# Uniform Mordell-Lang Plus Bogomolov

Tangli Ge  Department of Mathematics
Brown University
Box 1917
Providence, RI 02912
U.S.A<EMAIL_ADDRESS>
###### Abstract.

In this paper, we prove a uniform version of Poonen’s ”Mordell-Lang Plus
Bogomolov” theorem [10], based on Vojta’s method. We mainly generalize
Rémond’s work on large points to allow an extra $\epsilon$-neighborhood. The
part on small points follows from [6].

Work supported in part by funds from NSF grant DMS-2100548 and DMS-1759514

##  1\. Introduction

Throughout, $A$ is an abelian variety over $\bar{\mathbb{Q}}$ equipped with a
Néron-Tate height $\hat{h}$ and $\Gamma$ is a finitely generated subgroup of
$A(\bar{\mathbb{Q}})$. The _division group_ $\Gamma^{\prime}$ of $\Gamma$ is
defined as

$\Gamma^{\prime}:=\\{x\in A(\bar{\mathbb{Q}})|\text{ there exists }n\geq
1\text{ such that }nx\in\Gamma\\}.$

The Mordell-Lang conjecture, proved in a sequence of papers by Faltings, Vojta
and many others, states that if an integral subvariety $X$ of $A$ is not a
_coset_ (i.e. a translate of an abelian subvariety by a point), then
$X\cap\Gamma^{\prime}$111By which we mean
$X(\bar{\mathbb{Q}})\cap\Gamma^{\prime}$, intersecting as subsets of
$A(\bar{\mathbb{Q}})$. is not Zariski dense in $X$. On the other hand, the
Bogomolov conjecture proved by Ullmo and S. Zhang, says that if $X$ is not a
_torsion coset_ (i.e. a translate of an abelian subvariety by a torsion
point), then there is some $\epsilon>0$ such that the set of small points

$\\{P\in X(\bar{\mathbb{Q}}):\hat{h}(P)<\epsilon\\}$

is not Zariski dense in $X$.

Later, Poonen [10] showed that the Mordell-Lang conjecture and the Bogomolov
conjecture, together with an equidistribution theorem, imply a stronger
result, which trivially encompasses both conjectures. For $\epsilon>0$, define
the _$\epsilon$ -neighborhood_ $\Gamma^{\prime}_{\epsilon}$ of the division
group $\Gamma^{\prime}$ as

$\Gamma^{\prime}_{\epsilon}:=\\{\gamma+z:\gamma\in\Gamma^{\prime},z\in
A(\bar{\mathbb{Q}}),\hat{h}(z)<\epsilon\\}.$

What Poonen proved is the following

######  Theorem 1.1 (Poonen).

If $X\subseteq A$ is an integral subvariety of $A$ which is not a coset, and
$\Gamma\leq A(\bar{\mathbb{Q}})$ is a finitely generated subgroup, then there
is some $\epsilon=\epsilon(X,A,\Gamma)>0$ such that
$X\cap\Gamma^{\prime}_{\epsilon}$ is not dense in $X$.

A standard recursive application of the above theorem leads to the following
equivalent version

######  Theorem 1.1’ (Poonen).

If $X$ is an integral subvariety of $A$ and $\Gamma\leq A(\bar{\mathbb{Q}})$
is a finitely generated subgroup, then there is some
$\epsilon=\epsilon(X,A,\Gamma)$ such that the set
$X\cap\Gamma_{\epsilon}^{\prime}$ is contained in a finite union of cosets in
$X$.

Let $\operatorname{Sp}(X)$ denote the _special locus_ of $X$ (i.e. the union
of positive-dimensional cosets in $X$). Kawamata [7] showed
$\operatorname{Sp}(X)$ is a closed subvariety of $X$. Write
$X^{\circ}:=X-\operatorname{Sp}(X)$. Then all cosets in $X^{\circ}$ are points
and Theorem 1.1’ implies the finiteness of the set
$X^{\circ}\cap\Gamma^{\prime}_{\epsilon}$.

A motivating question for this paper is: _can we choose $\epsilon$ above to be
independent of the choice of $\Gamma$?_ The answer is yes and indeed we can
get a more uniform result, combining the uniform Mordell-Lang conjecture and
the uniform Bogomolov conjecture proved in [6].

Throughout, let $L$ be a symmetric ample line bundle on $A$ with the
associated Néron-Tate height $\hat{h}=\hat{h}_{L}$ and fix the following
notations:

$r:=\dim X,\,g:=\dim A,\,d:=\deg_{L}X,\,l:=\deg_{L}A.$

The main result of this paper is the following

######  Theorem 1.2.

For any integral subvariety $X\subseteq A$, there exist positive constants
$\epsilon=\epsilon(r,g,d)$ and $c=c(r,g,d)$ such that for any finitely
generated subgroup $\Gamma\leq A(\bar{\mathbb{Q}})$ of rank $\rho$, we have

$\\#X^{\circ}\cap\Gamma^{\prime}_{\epsilon}\leq c^{1+\rho}.$

######  Remark 1.3.

(1) Throughout, expressions such as $c=c(r,g,d)$ are used to mean the constant
$c$ is only related to $r,g,d$ in the right setting.

(2) The degree $l$ of $A$ only appears in the middle of the proof, which is
shown to become unnecessary, mainly because we can pass to the case where $X$
generates $A$. The dependence on $r=\dim X$ in the above theorem can also be
removed easily, by simply taking

$\epsilon(g,d):=\min_{0\leq r\leq g}\\{\epsilon(r,g,d)\\},\quad
c(g,d):=\max_{0\leq r\leq g}\\{c(r,g,d)\\}.$

But we decide to keep this stratification for easier inductive statements.

(3) The above theorems are weaker if we decrease $\epsilon$ or increase $c$,
but since our goal is to prove the existence, we will freely weaken the
results, to ease our notations. Thus without loss of generality we always make
the following assumptions

  * •

$\epsilon$ decreases in all three variables;

  * •

$c$ increases in all three variables;

  * •

$c(r,g,d_{1}+d_{2})\geq c(r,g,d_{1})+c(r,g,d_{2})$.

Then we can use the result even when $X$ is not irreducible or
equidimensional. For example, if $X=X_{1}\cup X_{2}$ with $X_{1},X_{2}$
irreducible of dimension $r$ and degree $d_{1},d_{2}$ respectively, then with
$\epsilon=\epsilon(r,g,d_{1}+d_{2})$, by the third condition above we have

$\\#X^{\circ}\cap\Gamma^{\prime}_{\epsilon}\leq\\#X_{1}^{\circ}\cap\Gamma^{\prime}_{\epsilon}+\\#X_{2}^{\circ}\cap\Gamma^{\prime}_{\epsilon}\leq
c(r,g,d_{1})^{1+\rho}+c_{2}(r,g,d_{2})^{1+\rho}\leq
c(r,g,d_{1}+d_{2})^{1+\rho}.$

The proof of Theorem 1.2 is based on Vojta’s method, which has a dichotomy of
large and small points. For the small points, we use a result of our previous
work [6] on the uniform Mordell-Lang conjecture, joint with Gao and Kühne. The
main part of this paper is to generalize the work of Rémond [11, 12] and
David-Philippon [3] on the large points to allow an extra
$\epsilon$-neighborhood. Many ideas in the proof are borrowed from their work.

Theorem 1.2 self-improves to a seemingly stronger version, in the flavor of
Theorem 1.1’, as follows, which is shown in §6.

######  Theorem 1.2’.

For any integral subvariety $X\subseteq A$, there exist positive constants
$\epsilon=\epsilon(g,d)$ and $c=c(g,d)$ such that for any finitely generated
subgroup $\Gamma\leq A(\bar{\mathbb{Q}})$ of rank $\rho$, the set
$X\cap\Gamma_{\epsilon}^{\prime}$ is contained in the union of at most
$c^{1+\rho}$ many cosets in $X$.

##  2\. Technical Lemmas

In this section, we prove several easy lemmas about Euclidean spaces. The
readers shall feel free to skip this section and come back only when a lemma
is invoked.

######  Lemma 2.1.

Let $V$ be a real vector space with an inner product. For $\theta\in(0,\pi)$,
there exists $0<\delta=\delta(\theta)<1$ with the following property: if
$v_{1},v_{2}\in V$ satisfy $|v_{1}|\geq c>0$ and $|v_{2}-v_{1}|\leq\delta\cdot
c$, then the angle between $v_{1},v_{2}$ is at most $\theta$.

###### Proof.

This is clear geometrically: if one looks out from the origin to $v_{1}$, then
a small enough ball at $v_{1}$ will stay within the angle of vision. To prove
it, take $\delta:=1-\frac{1}{2-\cos\theta}$. Then

$\frac{\langle
v_{1},v_{2}\rangle}{|v_{1}||v_{2}|}=\frac{|v_{1}|^{2}}{|v_{1}||v_{2}|}+\frac{\langle
v_{1},v_{2}-v_{1}\rangle}{|v_{1}||v_{2}|}\geq
1-\frac{|v_{1}||v_{2}-v_{1}|}{|v_{1}||v_{2}|}\geq 1-\frac{\epsilon\cdot
c}{c-\epsilon\cdot c}=\cos\theta.$

So the angle between $v_{1},v_{2}$ is at most $\theta$. ∎

######  Lemma 2.2.

[11, Corollaire 6.1] Let $V$ be a finite-dimensional real vector space with an
inner product, of dimension $\rho$. For any $c>1$, the vector spaces can be
covered by at most $(1+\sqrt{8c})^{\rho}$ regions, such that for any
$v_{1},v_{2}$ in a same region, we have

$\langle v_{1},v_{2}\rangle\geq(1-1/c)|v_{1}||v_{2}|.$

###### Proof.

We include the proof here for completeness.

Let $\theta:=\frac{1}{2}\arccos(1-1/c)$. Denote by $B(x,R)$, a closed ball of
radius $R$ centered at $x$. We aim to find a covering of the _unit sphere_ $S$
by pieces, such that the angle between any two points in a piece is at most
$2\theta$. Then we can just cover $V$ by the (one-sided) cones spanned by
these pieces. The strategy is to cover the sphere first by small balls
centered at points on the sphere, of radius $\sin\theta$. The piece cut out by
the intersection of the sphere and a small ball has the required property.
Indeed, the distance between any $v_{1},v_{2}$ in the piece is at most
$2\sin\theta$, which by an easy geometric argument in the isosceles triangle,
implies the angle between the vectors $v_{1},v_{2}$ is at most $2\theta$.

Now we construct our cover inductively as follows. Assuming that we have
chosen centers $x_{1},..,x_{n}$, and that

$S\not\subseteq\bigcup_{i=1}^{n}B(x_{i},\sin\theta).$

Then we pick $x_{n+1}$ in $S$ that is not yet covered. By compactness of $S$,
the procedure stops at a finite step. Assume eventually, we pick out
$x_{1},\ldots,x_{N}$, and no more point can be picked.

Notice that by our choice, the distance between any $x_{i},x_{j}$ for $i\neq
j$ is at least $\sin\theta$. So in particular, we have

$B(x_{i},\frac{1}{2}\sin\theta)\cap B(x_{j},\frac{1}{2}\sin\theta)=\emptyset.$

Hence

$\bigcup_{i=1}^{N}B(x_{i},\frac{1}{2}\sin\theta)\subseteq
B(0,1+\frac{1}{2}\sin\theta).$

Since $\operatorname{Vol}(B(0,R))=R^{\rho}\operatorname{Vol}(B(0,1))$, we get

$N\leq\left(\frac{1+\frac{1}{2}\sin\theta}{\frac{1}{2}\sin\theta}\right)^{\rho}=(1+2/\sin\theta)^{\rho}\leq(1+\sqrt{8c})^{\rho}.$

∎

######  Lemma 2.3.

[11, Lemme 6.1] Let $V$ be a finite-dimensional real vector space with an
inner product, of dimension $\rho$. Then a ball of radius $c$ can be covered
by at most $(1+2c/c^{\prime})^{\rho}$ balls of radius $c^{\prime}$.

###### Proof.

Same idea as the proof of Lemma 2.2. Exhaust points $x_{1},...,x_{N}\in
B(0,c)$ so that the distance between each pair is at least $c^{\prime}$. Then
$B(0,c)$ is covered by the balls of radius $c^{\prime}$ centered at $c_{i}$
for $i=1,\ldots,N$. Also, we have

$\bigcup_{i=1}^{N}B(x_{i},\frac{1}{2}c^{\prime})\subseteq
B(0,c+\frac{1}{2}c^{\prime}).$

Comparing the volumes, we get

$N\leq\left(\frac{c+\frac{1}{2}c^{\prime}}{\frac{1}{2}c^{\prime}}\right)^{\rho}=(1+2c/c^{\prime})^{\rho}.$

∎

##  3\. Large Points

In this section, we review results of Rémond and apply them to our setting for
a uniform treatment of large points. Many ideas are due to Rémond and our job
is to carefully take the $\epsilon$-neighborhood into account.

We assume $L$ to be moreover _very ample_ and induce a projectively normal
closed immersion into some projective space, for this section. It is not much
harder to show the general case, since if $L$ is ample then $L^{\otimes 4}$
satisfies our assumption, see for example [9]. We have $h^{0}(A,L)=l/g!$, see
[6, §2]. So $A$ can be embedded in $\mathbb{P}^{n}$ with $n=l/g!-1$.

One can define the height $h(X)$ of a subvariety $X\subseteq\mathbb{P}^{n}$
using the arithmetic intersection theory, see [2].

###  3.1. Inequalities

There are two important constants that appear in the work of Rémond, namely
$c_{\mathrm{NT}}$ and $h_{1}$. The first one $c_{\mathrm{NT}}$ is a bound
arising from the construction of Néron-Tate heights on the abelian variety. It
satisfies

$|\hat{h}_{L}(P)-h_{L}(P)|\leq c_{\mathrm{NT}}$

for any $P\in A(\bar{\mathbb{Q}})$. The second one $h_{1}$ is the Weil height
of the polynomials defining the addition and subtraction on the abelian
variety. It is known that there is a constant $c^{\prime}=c^{\prime}(g,l)$
such that

(*) $c_{\mathrm{NT}},h_{1}\leq c^{\prime}\max\\{1,h_{\mathrm{Fal}}(A)\\},$

see [3, (6.41)] and [4, (8.4)(8.7)].

The Néron-Tate height $\hat{h}=\hat{h}_{L}$ induces an inner product
$\langle\cdot,\cdot\rangle$ on the vector space
$A(\bar{\mathbb{Q}})\otimes_{\mathbb{Z}}\mathbb{R}$, so that for any point
$P\in A(\bar{\mathbb{Q}})$, we have $\langle P,P\rangle=\hat{h}(P)$. Write
$|P|:=\hat{h}(P)^{1/2}$.

Let $D_{X}:X^{r+1}\rightarrow A^{r}$ (recall that $r=\dim X$) be the morphism
defined by $(x_{0},\ldots,x_{r})\mapsto(x_{1}-x_{0},\ldots,x_{r}-x_{0})$. The
following theorem by Rémond gives explicit generalized Vojta’s inequality and
Mumford’s inequality.

######  Theorem 3.1 (Rémond).

Take any integral subvariety $X\subseteq A$. There exist constants
$c_{1}=c_{1}(r,g,d,l)>1$ and $c_{2}=c_{2}(r,g,d,l)>0$ with the following
property.

  1. (1)

(Vojta’s inequality) If $P_{0},\ldots,P_{\dim X}\in
X^{\circ}(\bar{\mathbb{Q}})$ satisfy

$\left\langle
P_{i},P_{i+1}\right\rangle\geq(1-\frac{1}{c_{1}})|P_{i}||P_{i+1}|\,\quad\text{and}\quad|P_{i+1}|\geq
c_{1}|P_{i}|,$

for any $i$, then

$|P_{0}|^{2}\leq c_{2}\max\\{1,h(X),h_{\mathrm{Fal}}(A)\\}.$

  2. (2)

(Mumford’s inequality) Suppose $(P_{0},\ldots,P_{r})$ is an isolated point in
the fiber of $D_{X}:X^{r+1}\rightarrow A^{r}$. If

$\left\langle
P_{0},P_{i}\right\rangle\geq(1-\frac{1}{c_{1}})|P_{0}||P_{i}|\,\quad\text{and}\quad||P_{0}|-|P_{i}||\leq\frac{1}{c_{1}}|P_{0}|,$

for any $i$, then

$|P_{0}|^{2}\leq c_{2}\max\\{1,h(X),h_{\mathrm{Fal}}(A)\\}.$

###### Proof.

Vojta’s inequality is [12, Théorème 1.1] and Mumford’s inequality is [11,
Proposition 3.4]. Note that we can remove $c_{\mathrm{NT}},h_{1}$ from them by
(* ‣ 3.1). ∎

The following proposition is similar to Rémond [11, Proposition 3.3]. It will
be used in Proposition 3.3 to ensure the extra condition in Mumford’s
inequality.

######  Proposition 3.2 (Rémond).

Let $\Xi\subseteq X^{\circ}(\bar{\mathbb{Q}})$ be a set of points. Assume
there is $P_{0}\in X(\bar{\mathbb{Q}})$ such that for any
$P_{1},\ldots,P_{r}\in\Xi$, the point $(P_{0},P_{1},\ldots,P_{r})$ is not
isolated in the fiber of $D_{X}:X^{r+1}\rightarrow A^{r}$. Then $\Xi$ is
contained in a Zariski closed subset $X^{\prime}\subsetneq X$ with
$\deg_{L}X^{\prime}<d^{r+2}$.

###### Proof.

If the dimension of the stabilizer $\operatorname{Stab}(X)$ of $X$ in $A$ is
not $0$, then every point of $X$ is on a nontrivial coset of $X$, whence
$X^{\circ}=\emptyset$. So we can assume $\operatorname{Stab}(X)$ is finite.

Notice that the fiber of $D_{X}$ over $(P_{1}-P_{0},\ldots,P_{r}-P_{0})$ is

$\\{(P_{0}+a,\ldots,P_{r}+a)\in X^{r+1}(\bar{\mathbb{Q}}):a\in
A(\bar{\mathbb{Q}})\\},$

which is isomorphic to

$\\{a\in A(\bar{\mathbb{Q}}):P_{0}+a,\ldots,P_{r}+a\in
X\\}=\bigcap_{i=0}^{r}(X-P_{i}).$

Thus the condition that $(P_{0},\ldots,P_{r})$ is isolated in the fiber is
equivalent to that the dimension of $\bigcap_{i=0}^{r}(X-P_{i})$ at the origin
is $0$. So by assumption, $\dim_{0}\bigcap_{i=0}^{r}(X-P_{i})\neq 0$ for any
choice of $P_{1},\ldots,P_{r}\in\Xi$. If we pick $P_{1},\ldots$ by induction
to reduce the dimension at $0$ of the intersection, then there is some
$r_{0}<r$ such that after we pick $P_{r_{0}}$, we cannot reduce the dimension
at $0$ in one step any more. In other words, if we let $C_{1},\ldots,C_{s}$ be
the top-dimensional irreducible components passing through $0$ of
$\bigcap_{i=0}^{r_{0}}(X-P_{i})$, then $X-Q$ must contain some $C_{i}$ for any
$Q\in\Xi$. On the other hand, $C_{i}\subseteq X-Q$ if and only if
$Q\in\bigcap_{a\in C_{i}(\bar{\mathbb{Q}})}(X-a).$ So we have

$\Xi\subseteq\bigcup_{i=1}^{s}\bigcap_{a\in C_{i}(\bar{\mathbb{Q}})}(X-a).$

Claim: $\bigcap_{a\in C_{i}(\bar{\mathbb{Q}})}(X-a)$ is contained in a proper
subvariety $X_{i}$ of $X$ of degree at most $d^{2}$. Indeed, since
$\operatorname{Stab}(X)$ is finite, there is some $a_{i}\in
C_{i}(\bar{\mathbb{Q}})$ such that $X-a_{i}\neq X$. So simply take
$X_{i}:=X\cap(X-a_{i})$. On the other hand, $s\leq d^{r}$ since
$\deg\bigcap_{i=0}^{r_{0}}(X-P_{i})\leq d^{r}$. Let $X^{\prime}$ be the union
of $X_{i}$. Then $\deg X^{\prime}\leq d^{r+2}$ and $\Xi\subseteq X^{\prime}$.
∎

###  3.2. Large points

In the proof of Theroem 1.2, we will use induction on the dimension of $X$. To
make things more clear, we separate the steps from the proof and make them
propositions.

######  Proposition 3.3.

Assume Theorem 1.2 holds for $\dim X\leq r-1$. For any $r$-dimensional
integral subvariety $X\subseteq A$, there exist positive constants
$\epsilon_{1}=\epsilon_{1}(r,g,d,l)$ and $c_{3}=c_{3}(r,g,d,l)$ such that for
any finitely generated subgroup $\Gamma\subseteq A(\bar{\mathbb{Q}})$ of rank
$\rho$, we have

$\\#\left\\{P\in
X^{\circ}\cap\Gamma_{\epsilon_{1}}^{\prime}:\hat{h}(P)>4c_{2}\max\\{1,h(X),h_{\mathrm{Fal}}(A)\\}\right\\}\leq
c_{3}^{1+\rho}$

where $c_{2}=c_{2}(r,g,d,l)$ is taken from Theorem 3.1.

###### Proof.

Consider the $\rho$-dimensional real vector space
$\Gamma\otimes\mathbb{R}=\Gamma^{\prime}\otimes\mathbb{R}$ embedded in
$A(\bar{\mathbb{Q}})\otimes\mathbb{R}$, equipped with the inner product
induced by the Néron-Tate height.

Take $c_{1}=c_{1}(r,g,d,l)$ from Theorem 3.1. Let
$\theta_{1}:=\frac{1}{2}[\arccos(1-\frac{1}{c_{1}})-\arccos(1-\frac{1}{2c_{1}})]$.
By Lemma 2.1 with $\theta=\theta_{1}$ and $c=\sqrt{c_{2}}$, there exists

$\epsilon_{1}=\left(\delta(\theta_{1})\cdot\sqrt{c_{2}}\right)^{2}=\epsilon_{1}(\theta_{1},c_{2})=\epsilon_{1}(c_{1},c_{2})=\epsilon_{1}(r,g,d,l),$

such that for any $v_{1},v_{2}\in A(\bar{\mathbb{Q}})\otimes\mathbb{R}$ with
$|v_{1}|\geq\sqrt{c_{2}}$ and $|v_{2}-v_{1}|<\sqrt{\epsilon_{1}}$, the angle
between $v_{1},v_{2}$ is at most $\theta_{1}$. We need to decrease
$\epsilon_{1}$ further soon.

By Lemma 2.2, the $\rho$-dimensional vector space can be covered by at most
$(1+4\sqrt{c_{1}})^{\rho}$ cones on which $\left\langle
w_{1},w_{2}\right\rangle\geq(1-\frac{1}{2c_{1}})|w_{1}||w_{2}|$. Suppose $D$
is one such cone. Let $D_{\epsilon_{1}}$ be the $\epsilon_{1}$-neighborhood of
$D$ in $A(\bar{\mathbb{Q}})\otimes\mathbb{R}$ and let $D_{\epsilon_{1}}^{+}$
be the part of large points $v\in D_{\epsilon_{1}}$ with

$|v|^{2}>4c_{2}\max\\{1,h(X),h_{\mathrm{Fal}}(A)\\}.$

Then for $v_{1},v_{2}\in D_{\epsilon_{1}}^{+}$, we _claim_ that $\left\langle
v_{1},v_{2}\right\rangle\geq(1-\frac{1}{c_{1}})|v_{1}||v_{2}|$. Indeed, by
definition, there is $w_{1},w_{2}\in D$ with
$|v_{i}-w_{i}|<\sqrt{\epsilon_{1}}$ for $i=1,2$. But

$|w_{i}|^{2}\geq(|v_{i}|-|v_{i}-w_{i}|)^{2}>(|v_{i}|-\sqrt{c_{2}})^{2}>c_{2}\max\\{1,h(X),h_{\mathrm{Fal}}(A)\\}.$

In particular $|w_{i}|\geq\sqrt{c_{2}}$. So the angle between $v_{i},w_{i}$ is
at most $\theta_{1}$ by the last paragraph, for $i=1,2$. But the angle between
$w_{1},w_{2}$ is at most $\arccos(1-\frac{1}{2c_{1}})$. Therefore by the
triangle inequality, the angle between $v_{1},v_{2}$ is at most
$2\theta_{1}+\arccos(1-\frac{1}{2c_{1}})=\arccos(1-\frac{1}{c_{1}})$, hence
the claim.

It then suffices to bound the number of points in $X^{\circ}\cap
D_{\epsilon_{1}}^{+}$. This is where we invoke the inequalities. In order to
use Mumford’s inequality, we also need to use the inductive hypothesis for
lower dimensions.

Specifically, let us take any sequence of distinct points
$|P_{1}|\leq|P_{2}|\leq\ldots$ in $X^{\circ}\cap D_{\epsilon_{1}}^{+}$ ordered
by their heights. Note that we do not even know the finiteness of the sequence
yet and in fact we may need to shrink $\epsilon_{1}$ to ensure that. Replace
$\epsilon_{1}$ by $\min\\{\epsilon_{1},\epsilon(r-1,g,d^{r+2})\\}$ and let
$N:=c(r-1,g,d^{r+2})^{\rho+1}$, where $\epsilon,c$ are the functions in
Theorem 1.2 for lower dimensions.

Claim: any subset $\Xi$ of $X^{\circ}\cap D_{\epsilon_{1}}^{+}$ with
cardinality $\geq N+1$ is not contained in any Zariski closed subset
$X^{\prime}\subsetneq X$ with $\deg_{L}X^{\prime}\leq d^{r+2}$. Indeed, if
$X^{\prime}\subsetneq X$ is a Zariski closed subset containing $\Xi$, then
$\Xi\subseteq X^{\prime}\cap X^{\circ}\subseteq(X^{\prime})^{\circ}$. So
$(X^{\prime})^{\circ}\cap\Gamma_{\epsilon_{1}}^{\prime}$ contains $N+1$
points, which implies $\deg_{L}X^{\prime}>d^{r+2}$.

So by Proposition 3.2 with

$\Xi:=\\{P_{j},P_{j+1},...,P_{j+N}\\},$

there is $Q_{1},...,Q_{r}\in\Xi$ such that $(P_{j},Q_{1},\ldots,Q_{r})$ is
isolated in $D_{X}:X^{r+1}\rightarrow A^{r}$ whence Mumford’s inequality
applies and we get

$|P_{j+N}|\geq|Q_{i}|>(1+\frac{1}{c_{1}})|P_{j}|\text{ for any }j.$

Take $M:=M(c_{1})$ such that $(1+\frac{1}{c_{1}})^{M}\geq c_{1}$. Then

$|P_{j+NM}|>(1+\frac{1}{c_{1}})|P_{j+{N(M-1)}}|>\ldots>(1+\frac{1}{c_{1}})^{M}|P_{j}|\geq
c_{1}|P_{j}|.$

Then we must have $\\#X^{\circ}\cap D_{\epsilon_{1}}^{+}\leq rNM$, since
otherwise the sequence

$P_{1},P_{1+NM},P_{1+2NM},\ldots,P_{1+rNM}$

would contradict Vojta’s inequality.

Overall, we see that

$\\#\left\\{P\in
X^{\circ}\cap\Gamma_{\epsilon_{1}}^{\prime}:\hat{h}(P)>4c_{2}\max\\{1,h(X),h_{\mathrm{Fal}}(A)\\}\right\\}\leq(1+4\sqrt{c_{1}})^{\rho}\cdot
rNM.$

The result follows by noticing that

$(1+4\sqrt{c_{1}})^{\rho}\cdot rNM=(1+4\sqrt{c_{1}})^{\rho}\cdot r\cdot
c(r-1,g,d^{2g})^{\rho+1}\cdot M(c_{1})\leq c_{3}^{1+\rho}$

for some $c_{3}=c_{3}(r,g,d,l)$.

∎

In particular, we get the following qualitative result as a corollary by
applying the uniform Bogomolov [6]. This finiteness result will be used later
in Proposition 3.6.

######  Proposition 3.4.

Assume Theorem 1.2 holds for $\dim X\leq r-1$. For any $r$-dimensional
integral subvariety $X\subseteq A$, there exists a constant
$\epsilon_{0}=\epsilon_{0}(r,g,d,l)>0$ such that for any finitely generated
subgroup $\Gamma\leq A(\bar{\mathbb{Q}})$, the set
$X^{\circ}\cap\Gamma^{\prime}_{\epsilon_{0}}$ is finite.

###### Proof.

By the uniform Bogomolov [6, Theorem 1.3], there is
$\epsilon=\epsilon(g,d)>0,c=c(g,d)>0$ such that for any $Q\in
A(\bar{\mathbb{Q}})$,

$\\#\\{P\in X^{\circ}(\bar{\mathbb{Q}}):\hat{h}(P-Q)\leq\epsilon\\}<c.$

Let $\epsilon_{0}:=\frac{1}{16}\min\\{\epsilon,\epsilon_{1}\\}$. By
Proposition 3.3, we just need to show that the set

$\left\\{P\in X^{\circ}\cap\Gamma_{\epsilon_{0}}^{\prime}:\hat{h}(P)\leq
4c_{2}\max\\{1,h(X),h_{\mathrm{Fal}}(A)\\}\right\\}$

is finite. For this, first cover the ball $B$ in $\Gamma\otimes\mathbb{R}$ of
radius

$\sqrt{4c_{2}\max\\{1,h(X),h_{\mathrm{Fal}}(A)\\}}$

by finitely many balls of radius $\sqrt{\epsilon_{0}}$. Then the
$\epsilon_{0}$-neighborhood $B_{\epsilon_{0}}$ is covered by the
$\epsilon_{0}$-neighborhoods of the finitely many small balls. For any two
points $P,Q$ in the $\epsilon_{0}$-neighborhood of a same small ball, we have

$|P-Q|\leq 2\sqrt{\epsilon_{0}}+2\sqrt{\epsilon_{0}}=4\sqrt{\epsilon_{0}}.$

So $\hat{h}(P-Q)\leq 16\epsilon_{0}\leq\epsilon$. Thus there are at most $c$
points in such a neighborhood. To conclude, we have finitely many regions and
in each region we have finitely many points. So we get finiteness. ∎

###  3.3. Removing $h(X)$

######  Lemma 3.5.

Assume $\Xi\subseteq X(\bar{\mathbb{Q}})$ is a finite set with the property
that any equidimensional subvariety $X^{\prime}\subseteq X$ of dimension $r-1$
containing $\Xi$ satisfies $\deg_{L}X^{\prime}>ld^{2}/g!$. Then

$h(X)\leq
d(l/g!+1)^{r+1}\cdot\left(\max_{P\in\Xi}\hat{h}(P)+3\log(l/g!)\right).$

###### Proof.

This is [11, Lemme 3.1] with $n=l/g!-1$. ∎

Using this lemma, we can remove $h(X)$ from Proposition 3.3. The idea is to
consider all translates of $X$ and find a relatively small height.

######  Proposition 3.6.

Assume Theorem 1.2 holds for $\dim X\leq r-1$. For any $r$-dimensional
integral subvariety $X\subseteq A$, there exist positive constants
$\epsilon_{2}=\epsilon_{2}(r,g,d,l)$, $c_{4}=c_{4}(r,g,d,l)$ and
$c_{5}=c_{5}(r,g,d,l)$ such that for any finitely generated subgroup
$\Gamma\subseteq A(\bar{\mathbb{Q}})$ of rank $\rho$, either

$\\#X^{\circ}\cap\Gamma^{\prime}_{\epsilon_{2}}\leq c_{4}^{1+\rho},$

or there exists $Q_{0}\in X^{\circ}\cap\Gamma^{\prime}_{\epsilon_{2}}$ such
that

$\\#\\{P\in
X^{\circ}\cap\Gamma^{\prime}_{\epsilon_{2}}:\hat{h}(P-Q_{0})>c_{5}\max\\{1,h_{\mathrm{Fal}}(A)\\}\\}\leq
c_{3}^{2+\rho}$

where $c_{3}=c_{3}(r,g,d,l)$ is taken from Proposition 3.3.

###### Proof.

Write $N:=c(r-1,g,ld^{2}/g!)^{2+\rho}+1$ and

$\epsilon_{2}:=\min\\{\epsilon_{0}(r,g,d,l),\epsilon_{1}(r,g,d,l),\epsilon(r-1,g,ld^{2}/g!)\\}$

where $\epsilon_{0},\epsilon_{1}$ are from Proposition 3.4 and Proposition 3.3
respectively.

Take any $Q\in X(\bar{\mathbb{Q}})$. If $P_{1},\ldots,P_{N}$ are distinct
points of $X^{\circ}\cap\Gamma_{\epsilon_{2}}^{\prime}$, then
$P_{1}-Q,\ldots,P_{N}-Q$ are distinct points of
$(X^{\circ}-Q)\cap\left\langle\Gamma,Q\right\rangle^{\prime}_{\epsilon_{2}}$,
where $\left\langle\Gamma,Q\right\rangle$ is the subgroup of
$A(\bar{\mathbb{Q}})$ generated by $\Gamma$ and $Q$. By Theorem 1.2, the set
$\Xi:=\\{P_{1}-Q,\ldots,P_{N}-Q\\}$ is not contained in any subvariety
$X^{\prime}\subsetneq X-Q$ with $\dim X^{\prime}\leq r-1$ and
$\deg_{L}X^{\prime}\leq ld^{2}/g!$, simply because
$(X^{\prime})^{\circ}\cap\left\langle\Gamma,Q\right\rangle^{\prime}_{\epsilon_{2}}$
does not contain so many points. Thus Lemma 3.5 applies to $\Xi$ and $X-Q$ and
we have

$h(X-Q)\leq d(l/g!+1)^{r+1}\cdot\left(\max_{1\leq i\leq
N}\hat{h}(P_{i}-Q)+3\log(l/g!)\right).$

Applying Proposition 3.3 to $X-Q$ and
$\left\langle\Gamma,Q\right\rangle^{\prime}_{\epsilon_{2}}$ with the above
height bound, we find the cardinality of

$\left\\{P-Q\in(X^{\circ}-Q)\cap\langle\Gamma,Q\rangle^{\prime}_{\epsilon_{2}}:\hat{h}(P-Q)>N_{1}\max_{1\leq
i\leq N}\hat{h}(P_{i}-Q)+N_{2}\max\\{1,h_{\mathrm{Fal}}(A)\\}\right\\}$

is at most $c_{3}^{2+\rho}$ for some $N_{1}=N_{1}(r,g,d,l)$ and
$N_{2}=N_{2}(r,g,d,l)$, which in particular implies that

(3.6.1) $\\#\left\\{P\in
X^{\circ}\cap\Gamma^{\prime}_{\epsilon_{2}}:\hat{h}(P-Q)>N_{1}\max_{1\leq
i\leq N}\hat{h}(P_{i}-Q)+N_{2}\max\\{1,h_{\mathrm{Fal}}(A)\\}\right\\}\leq
c_{3}^{2+\rho}$

since $\Gamma^{\prime}_{\epsilon_{2}}-Q$ is contained in
$\left\langle\Gamma,Q\right\rangle^{\prime}_{\epsilon_{2}}$.

Now let us restrict the choice of $Q$ in the finite set
$X^{\circ}\cap\Gamma^{\prime}_{\epsilon_{2}}$. For each $Q$, there is a
minimum $M=M(Q)\geq 0$ such that

$\\#\\{P\in X^{\circ}\cap\Gamma^{\prime}_{\epsilon_{2}}:\hat{h}(P-Q)>M\\}\leq
c_{3}^{2+\rho}.$

By the finiteness, we can pick the smallest $M_{0}$ and assume
$M_{0}=M(Q_{0})$ for some $Q_{0}\in
X^{\circ}\cap\Gamma^{\prime}_{\epsilon_{2}}$. We are going to show that
$M_{0}$ is bounded by a constant multiple of
$\max\\{1,h_{\mathrm{Fal}}(A)\\}$, with the constant only related to
$r,g,d,l$.

Consider the set $W:=\\{P\in
X^{\circ}\cap\Gamma^{\prime}_{\epsilon_{2}}:\hat{h}(P-Q_{0})\leq M_{0}\\}$.
Then $W$ is contained in the $\epsilon_{2}$-neighborhood of the
$(1+\rho)$-dimensional ball of radius $\sqrt{M_{0}}$ centered at $Q_{0}$ in
the vector space $\left\langle\Gamma,Q_{0}\right\rangle\otimes\mathbb{R}$. In
particular, by Lemma 2.3, $W$ can be covered by at most
$(1+8\sqrt{N_{1}})^{1+\rho}$ many $\epsilon_{2}$-neighborhood of small balls
of radius $\frac{\sqrt{M_{0}}}{4\sqrt{N_{1}}}$, centered in
$\left\langle\Gamma,Q_{0}\right\rangle\otimes\mathbb{R}$. Assume that

(3.6.2)
$\\#X^{\circ}\cap\Gamma^{\prime}_{\epsilon_{2}}>c_{3}^{2+\rho}+(N-1)\cdot(1+8\sqrt{N_{1}})^{1+\rho}.$

Then $\\#W>(N-1)\cdot(1+8\sqrt{N_{1}})^{1+\rho}$. By the Pigeonhole principle,
there exists one $\epsilon_{2}$-neighborhood of a small ball (call it
$D_{\epsilon_{2}}$) that contains at least $N$ points in $W$. Assume that
$P_{1},...,P_{N}\in D_{\epsilon_{2}}$ are distinct. Then

$|P_{i}-P_{1}|\leq
2\cdot\frac{\sqrt{M_{0}}}{4\sqrt{N_{1}}}+2\sqrt{\epsilon_{2}}$

for any $1\leq i\leq N$. Then by (3.6.1), we see that

$M(P_{1})\leq
N_{1}\cdot(2\cdot\frac{\sqrt{M_{0}}}{4\sqrt{N_{1}}}+2\epsilon_{2})^{2}+N_{2}\max\\{1,h_{\mathrm{Fal}}(A)\\}.$

So by our choice of $M_{0}$, we get

$M_{0}\leq N_{1}\cdot
2(\frac{M_{0}}{4N_{1}}+4\epsilon_{2})+N_{2}\max\\{1,h_{\mathrm{Fal}}(A)\\},$

from which we derive

(3.6.3) $M_{0}\leq
16N_{1}\cdot\epsilon_{2}+2N_{2}\max\\{1,h_{\mathrm{Fal}}(A)\\}.$

Finally, simply notice that the right hand side of (3.6.2) can be bounded by
$c_{4}^{1+\rho}$ for some $c_{4}=c_{4}(r,g,d,l)$ and the right hand side of
(3.6.3) can be bounded by $c_{5}\max\\{1,h_{\mathrm{Fal}}(A)\\}$ for some
$c_{5}=c_{5}(r,g,d,l)$. ∎

##  4\. Small Points

We say a subvariety $X\subseteq A$ _generates_ $A$, if $X-X$ is not contained
in any proper abelian subvariety of $A$. We need the following ”New Gap
Principle” to study small points.

######  Theorem 4.1.

[6, Theorem 1.2] For any irreducible subvariety $X\subseteq A$ that generates
$A$, there exist constants $c_{6}=c_{6}(g,d)>0$ and $c_{7}=c_{7}(g,d)>0$ such
that the set

$\Sigma:=\left\\{P\in X^{\circ}(\bar{\mathbb{Q}}):\hat{h}(P)\leq
c_{6}\max\\{1,h_{\mathrm{Fal}}(A)\\}\right\\}$

is contained in some Zariski closed subset $X^{\prime}\subsetneq X$ with
$\deg_{L}(X^{\prime})<c_{7}$.

######  Corollary 4.2.

Assume Theorem 1.2 holds for $\dim X\leq r-1$. For any irreducible subvariety
$X\subseteq A$ that generates $A$, there exist constants
$\epsilon_{3}=\epsilon_{3}(r,g,d)$ and $c_{8}=c_{8}(r,g,d)$ such that for any
finitely generated subgroup $\Gamma\leq A(\bar{\mathbb{Q}})$ of rank $\rho$
and any $Q\in A(\bar{\mathbb{Q}})$, we have

$\\#\left\\{P\in X^{\circ}\cap\Gamma^{\prime}_{\epsilon_{3}}:\hat{h}(P-Q)\leq
c_{6}\max\\{1,h_{\mathrm{Fal}}(A)\\}\right\\}\leq c_{8}^{1+\rho}.$

###### Proof.

Take $\epsilon_{3}:=\epsilon(r-1,g,c_{7})$ and $c_{8}=c(r-1,g,c_{7})^{2}$.
Note that for any subvariety $X^{\prime}\subseteq X$, we have $X^{\circ}\cap
X^{\prime}\subseteq(X^{\prime})^{\circ}$, since the special locus of $X$
contains the special locus of $X^{\prime}$ by definition. By Theorem 4.1, the
set

$\Sigma_{Q}:=\\{P\in X^{\circ}(\bar{\mathbb{Q}}):\hat{h}(P-Q)\leq
c_{6}\max\\{1,h_{\mathrm{Fal}}(A)\\}\\}$

is contained in some $X^{\prime}_{Q}\subsetneq X$ with
$\deg_{L}(X^{\prime}_{Q})<c_{7}$. By hypothesis, we have

$\\#(X^{\prime}_{Q})^{\circ}\cap\left\langle\Gamma,Q\right\rangle^{\prime}_{\epsilon_{3}}\leq
c(r-1,g,c_{7})^{2+\rho}\leq c_{8}^{1+\rho}$

for some $c_{8}=c_{8}(r,g,d)>0$. In particular, we get
$\\#\Sigma_{Q}\cap\Gamma^{\prime}_{\epsilon_{3}}\leq c_{8}^{1+\rho}$. ∎

##  5\. Proof of Theorem 1.2

We will construct $\epsilon(r,g,d)$ and $c(r,g,d)$ inductively on $\dim X$.

For $\dim X=0$, take $\epsilon(0,g,d)=\infty$ and $c(0,g,d)=d$. Then the
theorem holds trivially, and the assumption in Remark 1.3(3) is satisfied.

Assume the theorem holds for $\dim X\leq r-1$. Consider the case when $\dim
X=r$. Note that we can assume without loss of generality that $X$ generates
$A$. Indeed, if we can prove the case when $X$ generates $A$, simply replace
$A$ by the abelian subvariety $A^{\prime}$ generated by $X$ and $\Gamma$ by
$\Gamma\cap A^{\prime}(\bar{\mathbb{Q}})$, so that $g$ and $\rho$ decrease,
and the result follows trivially.

Let $\epsilon_{2},\epsilon_{3},c_{3},c_{4},c_{5},c_{6},c_{8}$ be as in
Proposition 3.6 and Corollary 4.2. Let
$\epsilon:=\min\\{\epsilon_{2},\epsilon_{3},\frac{1}{16}c_{6}\\}$. Assume
$\\#X^{\circ}\cap\Gamma^{\prime}_{\epsilon}>c_{4}^{1+\rho}$. Then by
Proposition 3.6, there exists $Q_{0}\in X^{\circ}\cap\Gamma$ such that

$\\#\left\\{P\in
X^{\circ}\cap\Gamma^{\prime}_{\epsilon}:\hat{h}(P-Q_{0})>c_{5}\max\\{1,h_{\mathrm{Fal}}(A)\\}\right\\}\leq
c_{3}^{2+\rho}.$

Consider the complement $\Sigma:=\left\\{P\in
X^{\circ}\cap\Gamma^{\prime}_{\epsilon}:\hat{h}(P-Q_{0})\leq
c_{5}\max\\{1,h_{\mathrm{Fal}}(A)\\}\right\\}$. Note that $\Sigma$ is
contained in the $\epsilon$-neighborhood of the $(1+\rho)$-dimensional ball of
radius $\sqrt{c_{5}\max\\{1,h_{\mathrm{Fal}}(A)\\}}$ centered at $Q_{0}$ in
the vector space $\left\langle\Gamma,Q_{0}\right\rangle\otimes\mathbb{R}$.
Cover $\Sigma$ using $\epsilon$-neighborhoods of small balls of radius
$\frac{1}{4}\sqrt{c_{6}\max\\{1,h_{\mathrm{Fal}}(A)\\}}$ centered in
$\left\langle\Gamma,Q_{0}\right\rangle\otimes\mathbb{R}$. By Lemma 2.3,
$\Sigma$ can be covered by $(1+8\sqrt{\frac{c_{5}}{c_{6}}})^{1+\rho}$ such
neighborhoods of the small balls. For $P_{1},P_{2}$ in a same
$\epsilon$-neighborhood, we have

$\hat{h}(P_{1}-P_{2})\leq\left(2\sqrt{\epsilon}+2\cdot\frac{1}{4}\sqrt{c_{6}\max\\{1,h_{\mathrm{Fal}}(A)\\}}\right)^{2}\leq
c_{6}\max\\{1,h_{\mathrm{Fal}}(A)\\}.$

Hence by Corollary 4.2, there are at most $c_{8}^{1+\rho}$ points of
$X^{\circ}\cap\Gamma^{\prime}_{\epsilon}$ in one $\epsilon$-neighborhood. So

$\\#X^{\circ}\cap\Gamma^{\prime}_{\epsilon}\leq\\#\Sigma+c_{3}^{2+\rho}\leq\left(1+8\sqrt{\frac{c_{5}}{c_{6}}}\right)^{1+\rho}\cdot
c_{8}^{1+\rho}+c_{3}^{2+\rho}\leq c^{1+\rho}$

for some $c=c(r,g,d,l)\geq c_{4}$.

Finally since $X$ generates $A$, the degree $l$ of $A$ is actually bounded by
a function of the degree $d$ of $X$ and dimension $g$ of $A$, see [6, §2]. So
we can remove the dependence on $l$ and we are done.

##  6\. Finiteness of Cosets

In this section, we show how Theorem 1.2 can be improved to Theorem 1.2’. The
idea is the same as in [5, Lemma 10.4]. Basically, we want to bound the
degrees of some subvarieties in the special locus and use induction.

###### Proof of Theorem 1.2’.

Without loss of generality, assume $X$ generates $A$. Let $\Sigma(X)$ be the
set of positive dimensional abelian subvarieties $B\subseteq A$ such that
there is $x\in X(\bar{\mathbb{Q}})$ satisfying $x+B\subseteq X$, and $B$ is
maximal for $x$. Bogomolov [1, Theorem 1] showes that there is an upper bound
$\delta_{1}=\delta_{1}(g,d)$ for the degree of $B\in\Sigma(X)$. Rémond [11,
Proposition 4.1] proves that there is $N_{1}:=N_{1}(g,l,\delta_{1}(g,d))$ such
that $\\#\Sigma(X)\leq N_{1}$.

The key idea is to take a complement $B^{\perp}$ of $B$, such that
$B+B^{\perp}=A$ and $B\cap B^{\perp}$ is finite. It is possible to choose such
a $B^{\perp}$ with degree at most $\delta_{2}=\delta_{2}(g,d,l)$, see [8]. The
$B^{\perp}$ will serve as a substitute for $A/B$. Write $(X:B):=\\{x\in
X:x+B\subseteq X\\}$. Note that (recall $r=\dim X$)

$(X:B)=\bigcap_{b\in B}(X+b)=\bigcap_{i=0}^{r}(X+b_{i})$

if we choose $b_{0},\ldots,b_{r}\in B$ in a general position, for dimension
reason. Then we let $X_{B}:=(X:B)\cap B^{\perp}.$ We have $X_{B}+B=(X:B)$. By
Bézout’s theorem, the degree of $X_{B}$ is bounded by
$d^{r+1}\cdot\delta_{2}\leq\delta_{3}=\delta_{3}(g,d,l)$. Note also that
$\operatorname{Sp}(X)$ can be written as a union

$\operatorname{Sp}(X)=\bigcup_{B\in\Sigma(X)}(X:B)=\bigcup_{B\in\Sigma(X)}(X_{B}^{\circ}+B),$

where the second inequality uses the fact that if $x+B^{\prime}\subseteq
X_{B}$, then

$x+(B+B^{\prime})\subseteq(X:(B+B^{\prime})).$

Take any finitely generated subgroup $\Gamma\subseteq A(\bar{\mathbb{Q}})$ of
rank $\rho$. For each $B\in\Sigma(X)$, we define $\Gamma_{B}\subseteq
B^{\perp}(\bar{\mathbb{Q}})$ to be the pullback of $\Gamma+B/B$ under the
isogeny $B^{\perp}\rightarrow A/B$. Then $\Gamma_{B}$ is of the same rank.
Note that
$(X_{B}^{\circ}+B)\cap\Gamma^{\prime}_{\epsilon}\subseteq(X_{B}^{\circ}\cap\Gamma_{B,\epsilon}^{\prime})+B$.

Applying Theorem 1.2 to $X_{B}$ and $\Gamma_{B}$, we get
$\epsilon=\epsilon(g,\delta_{3}),c=c(g,\delta_{3})$ such that (recall that we
can choose the constants in a way that it works for reducible varieties)
$\\#X_{B}^{\circ}\cap\Gamma^{\prime}_{B,\epsilon}\leq c^{1+\rho}.$ Then we
have

$\operatorname{Sp}(X)\cap\Gamma^{\prime}_{\epsilon}\subseteq\bigcup_{B\in\Sigma(X)}\left[(X_{B}^{\circ}\cap\Gamma_{B,\epsilon}^{\prime})+B\right],$

where the right hand side is the union of at most $\\#\Sigma(X)\cdot
c^{1+\rho}\leq N_{1}\cdot c^{1+\rho}$ cosets. Since $X$ generates $A$, we
could bound $l$ in terms of $g$ and $d$ and hence remove $l$ in a trivial way.
So we are done by simply combining the above result on $\operatorname{Sp}(X)$
with the result on $X^{\circ}$. ∎

##  7\. Further comments

In Theorem 1.2, $\epsilon$ is essentially only related to the dimension of the
abelian variety $A$ and the degree of the subvariety $X$. On the other hand,
as suggested by the New Gap Principle 4.1, the ”generic” distance between two
points on $X$ seems to be proportional to $\max\\{1,h_{\mathrm{Fal}}(B)\\}$,
where $B$ is the abelian subvariety generated by $X$. The exact same method
(except in Proposition 3.4, one needs to invoke NGP 4.1) can be used to show
the Theorem 1.2 is true with $\epsilon$ replaced by

$\epsilon\cdot\max\\{1,\inf_{B\subseteq A}h_{\mathrm{Fal}}(B)\\},$

where the infimum is taken over all positive-dimensional abelian subvarieties
$B$ of $A$.

Naturally one might ask whether we can take $\epsilon$ in the theorem to be
proportional to $\max\\{1,h_{\mathrm{Fal}}(A)\\}$. The same strategy does not
work in this case, mainly because the condition in the New Gap Principle 4.1
fails when we pass to subvarieties of $X$. But we cannot prove or disprove it.

## References

  * [1] F A Bogomolov.  Point of finite order on an abelian variety.  Mathematics of the USSR-Izvestiya, 17(1):55–72, 1981.
  * [2] J.-B. Bost, H. Gillet, and C. Soulé.  Heights of projective varieties and positive Green forms.  J. Amer. Math. Soc., 7(4):903–1027, 1994.
  * [3] Sinnou David and Patrice Philippon.  Minorations des hauteurs normalisées des sous-variétés des puissances des courbes elliptiques.  Int. Math. Res. Pap. IMRP, (3):Art. ID rpm006, 113, 2007.
  * [4] Vesselin Dimitrov, Ziyang Gao, and Philipp Habegger.  Uniformity in mordell-lang for curves.  accepted to Annals of Mathematics, 2021.
  * [5] Ziyang Gao.  Recent developments of the uniform mordell-lang conjecture.  available on arXiv, 2021.
  * [6] Ziyang Gao, Tangli Ge, and Lars Kühne.  The uniform mordell-lang conjecture.  available on arXiv, 2021.
  * [7] Yujiro Kawamata.  On Bloch’s conjecture.  Invent. Math., 57(1):97–100, 1980.
  * [8] David Masser and Gisbert Wüstholz.  Periods and minimal abelian subvarieties.  Ann. of Math. (2), 137(2):407–458, 1993.
  * [9] James S. Milne.  Abelian varieties (v2.00), 2008.  Available at www.jmilne.org/math/.
  * [10] Bjorn Poonen.  Mordell-Lang plus Bogomolov.  Invent. Math., 137(2):413–425, 1999.
  * [11] Gaël Rémond.  Décompte dans une conjecture de Lang.  Invent. Math., 142(3):513–545, 2000.
  * [12] Gaël Rémond.  Inégalité de Vojta en dimension supérieure.  Ann. Scuola Norm. Sup. Pisa Cl. Sci. (4), 29(1):101–151, 2000.


# Achievable Data Rate for URLLC-Enabled UAV Systems with 3-D Channel Model

Hong Ren, Cunhua Pan, Kezhi Wang, Yansha Deng, Maged Elkashlan, and Arumugam
Nallanathan This work is supported by the U.K. Engineering and the Physical
Sciences Research Council under Grant EP/R006466/1 and Grant EP/N029666/1.
(_Corresponding author: Cunhua Pan._)H. Ren, C. Pan, M. Elkashlan and A.
Nallanathan are with School of Electronic Engineering and Computer Science,
Queen Mary University of London, London, E1 4NS, U.K. (Email:h.ren, c.pan,
maged.elkashlan, a.nallanathan@qmul.ac.uk). K. Wang is with Department of
Computer and Information Sciences, Northumbria University, UK. (e-mail:
kezhi.wang@northumbria.ac.uk). Y. Deng is with the Department of Informatics,
King s College London, London WC2R 2LS, U.K. (e-mail:yansha.deng@kcl.ac.uk).

###### Abstract

In this paper, we investigate the average achievable data rate (AADR) of the
control information delivery from the ground control station (GCS) to
unmanned-aerial-vehicle (UAV) under a 3-D channel, which requires ultra-
reliable and low-latency communications (URLLC) to avoid collision. The value
of AADR can give insights on the packet size design. Achievable data rate
under short channel blocklength is adopted to characterize the system
performance. The UAV is assumed to be uniformly distributed within a
restricted space. We first adopt the Gaussian-Chebyshev quadrature (GCQ) to
approximate the exact AADR. The tight lower bound of AADR is derived in a
closed form. Numerical results verify the correctness and tightness of our
derived results.

##  I Introduction

UAV assisted wireless communication has attracted extensive research attention
from both academia and industria [1], due to their benefits of low cost, swift
deployment and high mobility. The link quality between UAV and ground users
(GUs) can be enhanced due to the high probability of line-of-sight (LoS)
communications.

Most of existing work mainly focused on the study of data transmission links
(i.e., UAV-to-GU and GU-to-UAV links), such as energy-efficient trajectory
design [2, 3], location optimization [4], and data services in emergency
networks [5, 6]. However, the control information delivery from the ground
control station (GCS) to the UAV introduce new challenges for UAV
communications since these links have stringent latency and reliable
requirements for supporting safety-critical functions [1], such as real-time
control to avoid collision. In general, very low data rate is enough to
exchange the control information between the GCS and the UAV. In contrast to
the conventional communications with relatively long transmission delay and
large packet size, small packet size should be delivered to support the
extremely low-latency transmission for control information delivery. In small
packet transmission, the Shannon’ capacity formula based on the law of large
numbers is no longer applicable, and decoding error probability cannot be
arbitrary small. In [7], the achievable data rate in finite blocklength regime
has been derived. Resource allocation for UAV communication with URLLC was
considered in [8].

However, the study on the performance analysis for the control information
delivery in UAV communications is still missing. Against this background, we
analyze the average achievable data rate for this transmission in UAV
communications under 3-D channel model. Two challenges will complicate the
analysis: the complicated data rate expression under short packet transmission
and the complicated 3-D channel model. The contributions of this paper can be
summarised as follows: 1) We are the first to study the average achievable
data rate (AADR) of control information delivery for a GCS-to-UAV
communication system under short packet transmission in 3-D channel model. It
can provide engineering insights on the packet size design; 2) The GCQ is
adopted to approximate the AADR; 3) The tight lower bound of AADR is derived
in closed form; 4) Simulation results verify the correctness and tightness of
our derived results.

##  II System Model

As shown in Fig. 1, we consider that a GCS sends remote control signals to a
UAV, which requires ultra-high reliability and ultra-low latency. Both GCS and
UAV are assumed to be equipped with single antenna. Without loss of
generality, we assume that the GCS is located at the center of the circle. To
guarantee that the UAV is within the GCS’s control area, we assume that the
UAV is flying within an inverted cone centered at GCC with the largest radius
of $D$. We also define a small inverted cone centered at GCS with radius $r$
($D>r$) that the UAV will not fly into. In addition, to avoid collision onto
the buildings or trees around the GCS, the elevation angle of the UAV denoted
as $\theta$ should be no smaller than $\theta_{\rm{min}}$ as shown in Fig. 1.
The UAV can fly freely in any direction in the space inside the large inverted
cone but outside the small inverted cone as shown in the shadow area in Fig.
1.

Figure 1: Illustration of the low-latency transmission of control signal from
the GCS to the UAV.

Then, the cumulative distribution function (CDF) of distance $d$ is

${F_{d}}(x)=\frac{{{x^{3}}-{r^{3}}}}{{{D^{3}}-{r^{3}}}},\ r\leq x\leq D$ (1)

and the probability distribution function (PDF) is

$\vspace{-0.1cm}{f_{d}}(x)=\frac{{d{F_{d}}(x)}}{{dx}}=\frac{{3{x^{2}}}}{{{D^{3}}-{r^{3}}}},r\leq
x\leq D.$ (2)

We adopt the 3-D channel model proposed in [4] which is more practical than
the widely used free space channel model. This model captures the fact that
the line-of-sight (LoS) probability increases with elevation angle. In
particular, the LoS probability is given by

$\vspace{-0.2cm}{P_{{\rm{LoS}}}}=\frac{1}{{1+a\exp\left({-b\left({\theta-a}\right)}\right)}},$
(3)

where $a$ and $b$ are positive constants that depend on the environment and
the values are given in [4]. For a given location of UAV, the mean path loss
is given by [4]:

$\vspace{-0.1cm}L(\theta,d)=\frac{A}{{1+a\exp\left({-b\left({\theta-a}\right)}\right)}}+20{\log_{10}}\left({{d}}\right)+C,$
(4)

where $A$ and $C$ are constants given by
$A=\eta_{{\rm{LoS}}}-\eta_{{\rm{NLoS}}}$ and
$C=20{\log_{10}}\left({\frac{{4\pi{f_{c}}}}{c}}\right)+{\eta_{{\rm{NLoS}}}}$,
respectively. The $\eta_{{\rm{LoS}}}$ and $\eta_{{\rm{NLoS}}}$ (in dB) are
respectively the losses corresponding to the LoS and non-LoS links. In
general, $\eta_{{\rm{NLoS}}}$ is much larger than $\eta_{{\rm{NLoS}}}$ due to
the severe path loss of NLoS. $f_{c}$ is the carrier frequency (Hz), and $c$
is the speed of light (m/s).

Assume that the transmission power from GCS to UAV is fixed as $P$ and the
noise power at UAV is denoted as ${\sigma^{2}}$, the signal-to-noise ratio
(SNR) at the UAV is given by

$\gamma(\theta,d)=\tilde{C}{d^{-2}}{e^{\frac{{\tilde{A}}}{{1+a\exp\left({-b(\theta-a)}\right)}}}}$
(5)

where $\tilde{A}=-A\frac{{\ln 10}}{{10}}>0$ and
$\tilde{C}=\frac{P}{{{\sigma^{2}}}}{10^{-\frac{C}{{10}}}}$.

For the control information delivery from the GCS to the UAV, the channel
blocklength is small. According to [7], for a simple point-to-point system
with finite blocklength $M$, to guarantee the minimum decoding error
probability of $\varepsilon$, the achievable data rate $R$ (bits per channel
use) can be approximately as

$\vspace{-0.15cm}R(\gamma(\theta,d))\\!\\!=\\!{{{\log}_{2}}\\!\left({1\\!+\\!\gamma(\theta,d)}\right)\\!-\\!\frac{1}{\text{ln}2}\\!\sqrt{\frac{V(\gamma(\theta,d))}{M}}{Q^{-1}}\\!\\!\left(\varepsilon\right)},$
(6)

where ${Q^{-1}}\left(\cdot\right)$ is the inverse function of
$Q\left(x\right)=\frac{1}{{\sqrt{2\pi}}}\int_{x}^{\infty}{{e^{-\frac{{{t^{2}}}}{2}}}}dt$,
and $V(\gamma)$ is the channel dispersion that is a function of SNR $\gamma$
and is given by $V(\gamma)=1-(1+\gamma)^{-2}$ [7]. The second term in (6) can
be regarded as the penalty on the data rate due to the short blocklength.

In the following, we aim to derive the exact average achievable data rate
(AADR) with fixed decoding error probability $\varepsilon$ when the UAV is
uniformly distributed in the space shown in Fig. 1, which is
$\bar{R}=\mathbb{E}{\\{R(\gamma(\theta,d))\\}}$. If the transmission needs to
be finished within $T_{\rm{max}}$ seconds and the system bandwidth is denoted
as $B$, the total number of channel uses is given by $M=BT_{\rm{max}}$. Then
the average number of bits that can be transmitted is calculated as
$L=BT_{\rm{max}}\bar{R}$, which is equal to the packet size. Therefore, the
AADR performance is vital, which can provide engineering insights for the
design of the packet size.

##  III Average Achievable Data Rate

The average achievable data rate (AADR) is written as

$\bar{R}=\int_{r}^{D}{\int_{\theta_{\rm{min}}}^{90}{R(\gamma(x,y)){f_{d,\theta}}(x,y)dy}}dx,$
(7)

where ${{f_{d,\theta}}(x,y)}$ is the joint PDF of $d$ and $\theta$. Since the
UAV is randomly deployed in the restricted space in Fig. 1, the PDF of
$\theta$ is given by
${f_{\theta}}(y)={1\mathord{\left/{\vphantom{1{\left({90-{\theta_{{\rm{min}}}}}\right)}}}\right.\kern-1.2pt}{\left({90-{\theta_{{\rm{min}}}}}\right)}}$.
In addition, since $d$ and $\theta$ are independent, the joint PDF of $d$ and
$\theta$ are given by ${f_{d,\theta}}(x,y)={f_{d}}(x){f_{\theta}}(y)$, where
${f_{d}}(x)$ is given in (2). In the following, we first use the GCQ method to
accurately approximate (7). Then, we derive its tight lower bound in closed
form.

###  III-A Approximate Expression

One can see that (7) can be rewritten as

$\vspace{-0.2cm}\bar{R}=\frac{1}{{90-{\theta_{{\rm{min}}}}}}\frac{3}{{{D^{3}}-{r^{3}}}}\int_{r}^{D}{\underbrace{\int_{{\theta_{{\rm{min}}}}}^{90}{{x^{2}}R(\gamma(y,x))dy}}_{{I_{1}}(x)}dx}.$
(8)

It is very difficult to find the closed-form expression of $I_{1}(x)$. We
adopt the GCQ [9] to approximate it. Define
${q_{1}}(x,y)={x^{2}}R(\gamma(y,x))$, we have

$\displaystyle\\!\\!\\!\\!\\!\\!{I_{1}}(x)\\!\\!\\!\\!\\!$ $\displaystyle=$
$\displaystyle\\!\\!\\!\\!\\!\\!\int_{{\theta_{{\rm{min}}}}}^{90}\\!\\!{{q_{1}}}(x,y)dy$
(9) $\displaystyle\approx$
$\displaystyle\\!\\!\\!\\!\\!\frac{{90-{\theta_{{\rm{min}}}}}}{2}\\!\sum\limits_{i=1}^{{N_{1}}}{{l_{i}}}\\!\cdot\\!{q_{1}}\\!\\!\left(\\!{\frac{{90\\!-\\!{\theta_{{\rm{min}}}}}}{2}{t_{i}}\\!+\\!\frac{{90\\!+\\!{\theta_{{\rm{min}}}}}}{2},x}\\!\\!\right)$
(10)

where $t_{i}$ is the $i$-th zero of Legendre polynomials, $N_{1}$ is the
number of terms, $l_{i}$ is the Gaussian weight given by Table (25.4) of [9].

Then, by substituting (10) into (8), one has

$\vspace{-0.1cm}\bar{R}=\frac{3}{{2}}\frac{{{1}}}{{{D^{3}}-{r^{3}}}}I_{2}$
(11)

where $I_{2}$ is given by

$\vspace{-0.1cm}{I_{2}}=\int_{r}^{D}{\underbrace{\sum\limits_{i=1}^{{N_{1}}}{{l_{i}}}{q_{1}}\left({\frac{{90-{\theta_{{\rm{min}}}}}}{2}{t_{i}}+\frac{{90+{\theta_{{\rm{min}}}}}}{2},x}\right)}_{{q_{2}}(x)}}dx$
(12)

By using the similar method, one can approximate ${I_{2}}$ as

$I_{2}\approx\frac{D-r}{2}\sum_{i=1}^{N_{2}}k_{i}\cdot
q_{2}\left(\frac{D-r}{2}g_{i}+\frac{D+r}{2}\right),$ (13)

where $g_{i}$, $N_{2}$ and $k_{i}$ are similarly defined as in (10).

Finally, by substituting (13) into (11), we have

$\displaystyle\bar{R}\approx\frac{3}{{4}}\frac{{{D-r}}}{{{D^{3}}-{r^{3}}}}\sum_{i=1}^{N_{2}}k_{i}\cdot
q_{2}\left(\frac{D-r}{2}g_{i}+\frac{D+r}{2}\right).$ (14)

###  III-B Lower Bound of AADR

In the following, we aim to derive the lower bound (LB) of the AADR in closed
form. To this end, we first introduce the following function

$\vspace{-0.2cm}f(x)=\ln\left({1+\frac{1}{x}}\right)-q\sqrt{\frac{{2x+1}}{{{{(x+1)}^{2}}}}},x>0$
(15)

where $q$ is a positive constant. Then, we have the following lemma:

_Lemma 1_ : $f(x)$ is always non-negative when $0<x\leq g^{-1}(q)$, where
$g^{-1}(q)$ is the inverse function of $g(x)$ which is defined in (21).

_Proof_ : Please refer to Appendix A.

In the following lemma, we show more properties of $f(x)$.

_Lemma 2_ : $f(x)$ is a decreasing and convex function when $0<x\leq
g^{-1}(q)$.

_Proof_ : Please refer to Appendix B.

Based on Lemma 2, we start to derive the LB of the AADR. In particular,
$R(\gamma)$ 111For notation simplicity, $\gamma$ means $\gamma(\theta,d)$ in
the following derivations. can be rewritten as

$\vspace{-0.2cm}R(\gamma)=\frac{1}{{\ln 2}}f\left({\frac{1}{\gamma}}\right)$
(16)

where $f(\cdot)$ is defined in (15) with
${q}=\frac{{{Q^{-1}}({\varepsilon})}}{{\sqrt{M}}}.$ Hence, if
$\gamma\geq{1\mathord{\left/{\vphantom{1{{g^{-1}}(q)}}}\right.\kern-1.2pt}{{g^{-1}}(q)}}$,
$f(\cdot)$ is a convex function. In our considered system, the minimum
$\gamma$ is achieved when $d=D$ and $\theta=0$ based on (5), and the minimum
value is
${\gamma_{\min}}=\tilde{C}{D^{-2}}{e^{\frac{{\tilde{A}}}{{1+a\exp\left({ab}\right)}}}}$.
This imposes the constraint for the maximum transmission distance between the
UAV and the GCS, which is given by

$\vspace{-0.1cm}D\leq\sqrt{\tilde{C}{e^{\frac{{\tilde{A}}}{{1+a\exp\left({ab}\right)}}}}{g^{-1}}(q)}\buildrel\Delta\over{=}{D_{\max}}$
(17)

By using the parameters in the simulation section, the maximum distance
${D_{\max}}$ can be up to 56.4 km and 56.8 km for Dense Urban and Suburban
scenarios [10], respectively, which are far beyond the control distance for
UAV. As a result, condition (17) always holds in practice. Then, $f(\cdot)$ is
a convex function when $r\leq d\leq D$ and $\theta_{\rm{min}}\leq\theta\leq
90$. Then, we have

$\vspace{-0.1cm}\mathbb{E}\\{R(\gamma)\\}\\!\\!=\\!\\!\frac{1}{{\ln
2}}\mathbb{E}\left\\{{f\left({\frac{1}{\gamma}}\right)}\right\\}\\!\\!\geq\\!\\!\frac{1}{{\ln
2}}f\left(\mathbb{E}{\left({\frac{1}{\gamma}}\right)}\right)\buildrel\Delta\\!\over{=}\\!\\!{R_{{\rm{lb}}}}.$
(18)

To obtain ${R_{{\rm{lb}}}}$, we only need to derive
$\mathbb{E}{\left({\frac{1}{\gamma}}\right)}$, which is much more tractable
than directly deriving the exact AADR.

The expression of $\mathbb{E}{\left({\frac{1}{\gamma}}\right)}$ is given by

$\displaystyle\mathbb{E}\left({\frac{1}{\gamma}}\right)=\frac{{{{3\tilde{C}}^{-1}}}}{{\left(90-\theta_{\rm{min}}\right)\left({{D^{3}}-{r^{3}}}\right)}}\cdot$
(19)
$\displaystyle\qquad\qquad\underbrace{\int_{r}^{D}{{x^{4}}dx}}_{U}\underbrace{\int_{\theta_{\rm{min}}}^{90}{{e^{-\frac{{\tilde{A}}}{{1+a\exp\left({-b\left({y-a}\right)}\right)}}}}dy}}_{V}.$

where $U$ can be readily calculated as
$U=\frac{1}{5}\left({{D^{5}}-{r^{5}}}\right)$. By using variable
substitutions, (3.351.5) and (3.352.5) of [11], as well as some simple
manipulations, one can have

$\vspace{-0.1cm}V=\frac{{\tilde{A}}}{b}\left({T({y_{1}})-T({y_{2}})}\right)$
(20)

where
${y_{1}}=\frac{{1+a{\rm{exp}}(-b({\theta_{\rm{min}}}-a))}}{{\tilde{A}}}$,
${y_{2}}=\frac{{1+a{\rm{exp}}(-b(90-a))}}{{\tilde{A}}}$,
$T(x)=\frac{e^{-\tilde{A}}\text{Ei}\left(\tilde{A}-\frac{1}{x}\right)}{\tilde{A}}-\frac{\text{Ei}\left(-\frac{1}{x}\right)}{\tilde{A}}$
and $\text{Ei}(z)=-\int_{-z}^{\infty}\frac{e^{-t}}{t}\,dt$ [11]. Then, one can
obtain the lower bound of $\bar{R}$ by inserting (19) into (18).

##  IV Simulation

In this section, simulation results are presented to verify the correctness of
our derived results. The simulation parameters are set as: $r=250$ m, $D=400$
m, $P=-20$ dB, $\sigma^{2}=-173$ dBm/Hz, $B=1$ MHz, $f_{c}=2.5$ GHz, and
$c=3\cdot 10^{8}$ m/s. Two scenarios are considered: dense urban and suburban.
The values of the corresponding parameters can be found in [10]. The minimum
elevation angle $\theta_{\rm{min}}$ is set to be 45 and 30 for dense urban and
suburban, respectively. This is reasonable since the former scenario has
higher density of obstacles than the latter one. Four curves are plotted: 1)
The average Shannon Capacity (‘Shannon’), which is equal to
$\mathbb{E}{\\{{{\log}_{2}}\left({1+\gamma(\theta,d)}\right)\\}}$. The value
is obtained by averaging over $10^{4}$ random UAV locations; 2) The
approximate value of AADR obtained by using the GCQ method (‘Chebyshev’),
which is given in (14); 3) The simulated AADR (‘Simulation’), which is equal
to $\bar{R}=\mathbb{E}{\\{R(\gamma(\theta,d))\\}}$. Its value is obtained by
averaging over $10^{4}$ random UAV locations; 4) The lower bound of AADR
(‘LB’) given in (18).

Figure 2: AADR versus $M$ for two different scenarios.

In Fig. 2, we first investigate the impact of channel blocklength $M$ on the
AADR performance with the decoding error probability fixed at
$\varepsilon=10^{-9}$. The channel blocklength $M$ ranges from 100 to 1000,
and thus the corresponding latency ranges from 0.1 ms to 1 ms, which satisfies
the low latency requirement. From Fig. 2, the AADR is observed to increase
with $M$ and approach the Shannon’s capacity. The reason is that with the
increase of $M$, the second term in (6) diminishes, which reduces to the
Shannon’s capacity formula. However, when $M$ is small, there is a big gap
between the conventional Shannon’s capacity and the AADR. This means that if
directly adopting the Shannon’s capacity as the performance measure, we will
overestimate the system performance, which may cause unexpected incidents.
Hence, we should adopt the short packet capacity to design the system. In Fig.
2, the results obtained by the GCQ method match very well with the simulation
results. Furthermore, the gap between the ‘LB’ and the ‘Simulation’ is very
small, especially in the case of the suburban scenario. These results verify
the correctness of our derived results.

Figure 3: AADR versus $\varepsilon$ for two different scenarios.

In Fig. 3, we investigate the impact of the decoding error probability
$\varepsilon$ on the AADR performance where channel blocklength is set as
$M=200$. It is seen from this figure that the AADR is increasing with
$\varepsilon$. This can be explained as follows: Function ${Q^{-1}}(x)$ is a
monotonically decreasing function of $x$. When the number of bits needed to
transmit is large, the decoding error probability is high accordingly for both
the same SNR and channel blocklength. There is big gap between the Shannon’s
capacity and the AADR, especially when $\varepsilon$ is very low. The
numerical results obtained by the GCQ method coincide with the simulated AADR,
and the gap between LB and the simulated AADR is small especially when
$\varepsilon$ is very low. This means that for highly reliable communications,
the capacity under short channel blocklength should be adopted.

##  V Conclusions

In this letter, we have studied the AADR of a UAV communication system under
short packet transmission using 3-D channel model. We have used the GCQ method
to derive the approximate expression of the AADR. Then, a tight lower bound of
AADR has been derived in closed form. These results are insightful for packet
size design when guaranteeing a minimum decoding error probability target.
Simulation results verify the correctness and the tightness of our derived
results.

##  Appendix A Proof of Lemma 1

To guarantee that $f(x)$ is always non-negative, we must have

$q\leq\frac{{(x+1)\ln\left({1+\frac{1}{x}}\right)}}{{\sqrt{2x+1}}}\buildrel\Delta\over{=}g(x).$
(21)

The first-order derivative of $g(x)$ with respect to $x$ is given by

$g^{\prime}(x)=\frac{{-2-\frac{1}{x}+x\ln\left({1+\frac{1}{x}}\right)}}{{{{\left({2x+1}\right)}^{\frac{3}{2}}}}}\leq\frac{{-1-\frac{1}{x}}}{{{{\left({2x+1}\right)}^{\frac{3}{2}}}}}<0$
(22)

where the second inequality follows by using
$\ln\left({1+\frac{1}{x}}\right)<\frac{1}{x}$. Hence, $g(x)$ is a
monotonically decreasing function of $x$. Then, the inequality in (21) holds
when $0<x\leq g^{-1}(q)$, which completes the proof.

##  Appendix B Proof of Lemma 2

The first-order derivative of $f(x)$ with respect to (w.r.t.) $x$ is given by

$f^{\prime}(x)=\frac{1}{{1+x}}-\frac{1}{x}-\frac{q}{{{{\left({x+1}\right)}^{2}}\sqrt{2x+1}}}+\frac{{q\sqrt{2x+1}}}{{{{\left({x+1}\right)}^{2}}}}.$
(23)

To prove the monotonically decreasing property of $f(x)$, $f^{\prime}(x)$
should be smaller than zero. Then, it should satisfy

$q<\frac{{(1+x)\sqrt{2x+1}}}{{2{x^{2}}}}\buildrel\Delta\over{=}{g_{1}}(x).$
(24)

Next, we show that ${g_{1}}(x)>{g}(x)$ for any $x$:

$\displaystyle\vspace{-0.2cm}{g_{1}}(x)$ $\displaystyle>$
$\displaystyle\frac{{(1+x)\sqrt{2x+1}\ln\left({1+\frac{1}{x}}\right)}}{{2x}}$
(25) $\displaystyle>$
$\displaystyle\frac{{(1+x)\sqrt{2x+1}\ln\left({1+\frac{1}{x}}\right)}}{{2x+1}}$
(26) $\displaystyle=$ $\displaystyle g(x)$ (27)

where (25) follows by using the relation
$\ln\left({1+\frac{1}{x}}\right)<\frac{1}{x}$. Since $0<x\leq g^{-1}(q)$, we
have $q\leq g(x)<{g_{1}}(x)$. As a result, $f(x)$ is a monotonically
decreasing function when $0<x\leq g^{-1}(q)$. The second-order derivative of
$f(x)$ w.r.t. $x$ is given by

$f^{\prime\prime}(x)=\frac{{(x+1){{(2x+1)}^{\frac{5}{2}}}-2q{x^{2}}\left({3{x^{2}}-1}\right)}}{{{x^{2}}{{(x+1)}^{3}}{{(2x+1)}^{\frac{3}{2}}}}}.$
(28)

If
$0<x\leq{1\mathord{\left/{\vphantom{1{\sqrt{3}}}}\right.\kern-1.2pt}{\sqrt{3}}}$,
$f^{\prime\prime}(x)>0$ since $a$ is a positive value. Hence, $f(x)$ is a
convex function for
$0<x\leq{1\mathord{\left/{\vphantom{1{\sqrt{3}}}}\right.\kern-1.2pt}{\sqrt{3}}}$.
Next, we check the region
$x>{1\mathord{\left/{\vphantom{1{\sqrt{3}}}}\right.\kern-1.2pt}{\sqrt{3}}}$.
In this case, to prove the convexity of $f(x)$, we need to show that
$f^{\prime\prime}(x)>0$ when
$x>{1\mathord{\left/{\vphantom{1{\sqrt{3}}}}\right.\kern-1.2pt}{\sqrt{3}}}$,
which yields

$q<\frac{{(x+1){{(2x+1)}^{\frac{5}{2}}}}}{{2{x^{2}}\left({3{x^{2}}-1}\right)}}\buildrel\Delta\over{=}{g_{2}}(x).$
(29)

Next, we prove that ${g_{2}}(x)>g(x)$ as follows:

$\begin{array}[]{l}{g_{2}}(x)=\frac{{x+1}}{{x\sqrt{2x+1}}}\frac{{{{(2x+1)}^{3}}}}{{2x(3{x^{2}}-1)}}>\\\
\frac{{x+1}}{{x\sqrt{2x+1}}}\frac{{{{(2x+1)}^{3}}}}{{6{x^{3}}}}>\frac{{x+1}}{{x\sqrt{2x+1}}}>g(x).\end{array}$
(30)

Hence, ${g_{2}}(x)>q$ and $f(x)$ is also a convex function over
$x>{1\mathord{\left/{\vphantom{1{\sqrt{3}}}}\right.\kern-1.2pt}{\sqrt{3}}}$.
Based on the above two cases, function $f(x)$ is a convex function over the
entire region when $0<x\leq g^{-1}(q)$.

## References

  * [1] Y. Zeng, R. Zhang, and T. J. Lim, “Wireless communications with unmanned aerial vehicles: opportunities and challenges,” _IEEE Commun. Mag._ , vol. 54, no. 5, pp. 36–42, May 2016.
  * [2] Y. Zeng and R. Zhang, “Energy-efficient UAV communication with trajectory optimization,” _IEEE Trans. Wireless Commun._ , vol. 16, no. 6, pp. 3747–3760, Jun. 2017.
  * [3] C. Pan, H. Ren, Y. Deng, M. Elkashlan, and A. Nallanathan, “Joint blocklength and location optimization for URLLC-enabled UAV relay systems,” _IEEE Commun. Lett._ , vol. 23, no. 3, pp. 498–501, Mar. 2019\.
  * [4] A. Al-Hourani, S. Kandeepan, and S. Lardner, “Optimal lap altitude for maximum coverage,” _IEEE Wirel. Commun. Lett._ , vol. 3, no. 6, pp. 569–572, Dec. 2014.
  * [5] N. Zhao, W. Lu, M. Sheng, Y. Chen, J. Tang, F. R. Yu, and K. Wong, “UAV-assisted emergency networks in disasters,” _IEEE Wireless Commun._ , vol. 26, no. 1, pp. 45–51, Feb. 2019.
  * [6] F. Cheng, S. Zhang, Z. Li, Y. Chen, N. Zhao, F. R. Yu, and V. C. M. Leung, “UAV trajectory optimization for data offloading at the edge of multiple cells,” _IEEE Trans. Veh. Technol._ , vol. 67, no. 7, pp. 6732–6736, Jul. 2018.
  * [7] Y. Polyanskiy, H. V. Poor, and S. Verdu, “Channel coding rate in the finite blocklength regime,” _IEEE Trans. Inf. Theory_ , vol. 56, no. 5, pp. 2307–2359, May 2010.
  * [8] C. She, C. Liu, T. Q. S. Quek, C. Yang, and Y. Li, “Ultra-reliable and low-latency communications in unmanned aerial vehicle communication systems,” _IEEE Trans. Commun._ , vol. 67, no. 5, pp. 3768–3781, May 2019\.
  * [9] M. Abramowitz and I. A. Stegun, _Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th ed._ Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 1972.
  * [10] R. I. Bor-Yaliniz, A. El-Keyi, and H. Yanikomeroglu, “Efficient 3-D placement of an aerial base station in next generation cellular networks,” in _2016 IEEE ICC_. IEEE, 2016, pp. 1–5.
  * [11] I. S. Gradshteyn and I. M. Ryzhik, _Table of Integrals, Series, and Products, 7th ed_. San Diego, CA: Academic, 2007.


* [38] B. Shaya, Process handling: A study for optimizing the processes for sourcing it and managing software licenses, Master Thesis Industrial Economics and Management (Dept.), KTH, Sweden.
  * [39] G. Gangadharan, L. Uden, P. Luttighuis, Sourcing Requirements and Designs for Software as a Service, International Journal of Systems and Service-Oriented Engineering 6 (1) (2016) 1–16.
  * [40] A. Maglyas, S. Fricker, The preliminary results from the software product management state-of-practice survey, in: C. Lassenius, K. Smolander (Eds.), International Conference on Software Business, Paphos, Cyprus, 2014, pp. 295–300.
  * [41] D. Méndez Fernández, S. Wagner, K. Lochmann, A. Baumann, H. de Carne, Field study on requirements engineering: Investigation of artifacts, project parameters, and execution strategies, Information and Software Technology 54 (2) (2012) 162–178.
  * [42] W. Bekkers, I. van de Weerd, M. Spruit, S. Brinkkemper, A framework for process improvement in software product management, in: European Conference on Software Process Improvement, Springer, 2010, pp. 1–12.
  * [43] D. M. Fernández, B. Penzenstadler, M. Kuhrmann, M. Broy, A meta model for artefact-orientation: Fundamentals and lessons learned in requirements engineering, no. 6395 in Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2010, pp. 183–197.
  * [44] T. Alspaugh, W. Scacchi, et al., Ongoing software development without classical requirements, in: 21st IEEE International Requirements Engineering Conference, IEEE, 2013, pp. 165–174.
  * [45] N. Ernst, G. Murphy, Case studies in just-in-time requirements analysis, in: IEEE Second International Workshop on Empirical Requirements Engineering, IEEE, 2012, pp. 25–32.
  * [46] W. Scacchi, Understanding the requirements for developing open source software systems, in: Software, IEE Proceedings-, Vol. 149, IET, 2002, pp. 24–39.
  * [47] J. Henkel, S. Schöberl, O. Alexy, The emergence of openness: How and why firms adopt selective revealing in open innovation, Research Policy 43 (5) (2014) 879–890.
  * [48] K. Pohl, G. Böckle, F. Linden, Software Product Line Engineering: Foundations, Principles and Techniques, Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2005.
  * [49] R. Kemp, Open source software (oss) governance in the organisation, Computer Law & Security Review 26 (3) (2010) 309–316.
  * [50] M. Komssi, M. Kauppinen, H. Töhönen, L. Lehtola, A. Davis, Roadmapping problems in practice: value creation from the perspective of the customers, Requirements Engineering 20 (1) (2015) 45–69.
  * [51] D. Damian, Stakeholders in global requirements engineering: Lessons learned from practice, Software, IEEE 24 (2) (2007) 21–27.
  * [52] L. Karlsson, G. Dahlstedt, B. Regnell, J. N. och Dag, A. Persson, Requirements engineering challenges in market-driven software development – an interview study with practitioners, Information and Software Technology 49 (6) (2007) 588 – 604, qualitative Software Engineering Research.
  * [53] B. Regnell, S. Brinkkemper, Market-driven requirements engineering for software products, in: Engineering and managing software requirements, Springer, 2005, pp. 287–308.
  * [54] K. Wnuk, B. Regnell, B. Berenbach, Scaling up requirements engineering – exploring the challenges of increasing size and complexity in market-driven software development, Springer Berlin Heidelberg, Berlin, Heidelberg, 2011, pp. 54–59.
  * [55] A. Hevner, S. March, J. Park, S. Ram, Design science in information systems research, MIS Q. 28 (1) (2004) 75–105.
  * [56] P. Runeson, M. Höst, A. Rainer, B. Regnell, Case Study Research in Software Engineering - Guidelines and Examples, Wiley, 2012.
  * [57] K. Nakakoji, Y. Yamamoto, Y. Nishinaka, K. Kishida, Y. Ye, Evolution patterns of open-source software systems and communities, in: Proceedings of the international workshop on Principles of software evolution, ACM, 2002, pp. 76–85.
  * [58] M. Khurum, T. Gorschek, M. Wilson, The software value map â€” an exhaustive collection of value aspects for the development of software intensive products, Journal of Software: Evolution and Process 25 (7) (2013) 711–741.
  * [59] A. Aurum, C. Wohlin, A value-based approach in requirements engineering: Explaining some of the fundamental concepts, Springer Berlin Heidelberg, Berlin, Heidelberg, 2007, pp. 109–115.
  * [60] T. Gorschek, P. Garre, S. Larsson, C. Wohlin, A model for technology transfer in practice, IEEE software 23 (6) (2006) 88–95.
  * [61] P. Runeson, M. Höst, Guidelines for conducting and reporting case study research in software engineering, Empirical software engineering 14 (2) (2009) 131–164.
  * [62] B. Flyvbjerg, Five misunderstandings about case-study research, in: Qualitative Research Practice, concise paperback Edition, SAGE, 2007, pp. 390–404.
  * [63] P. Runeson, M. Höst, A. Rainer, B. Regnell, Case Study Research in Software Engineering - Guidelines and Examples, Wiley, 2012.
  * [64] M. Poikselkä, H. Holma, J. Hongisto, J. Kallio, A. Toskala, Voice over LTE (VoLTE), John Wiley & Sons, 2012.
  * [65] J. Linåker, H. Munir, P. Runeson, B. Regnell, C. Schrewelius, A Survey on the Perception of Innovation in a Large Product-focused Software Organization, 6th International Conference on Software Business - ICSOB.


#  Overview
Computer Supported Query Formulation
Asymetrix Report 94-5

H.A. Proper
Asymetrix Research Laboratory
Department of Computer Science
University of Queensland
Australia 4072
<EMAIL_ADDRESS>
(Version of at 17:02)

Published as:

> H.A. (Erik) Proper. An Overview of Computer Supported Query Formulation.
> Technical report, Asymetrix Research Laboratory, University of Queensland,
> Brisbane, Queensland, Australia, 1994.

##  1 Introduction

Most present day organisations make use of some automated information system.
This usually means that a large body of vital corporate information is stored
in these information systems. As a result, an essential function of
information systems should be the support of disclosure of this information.

We purposely use the term information disclosure in this context. When using
the term information disclosure we envision a computer supported mechanism
that allows for an easy and intuitive formulation of queries in a language
that is as close to the user’s perception of the universe of discourse as
possible. From this point of view, it is only obvious that we do not consider
a simple query mechanism where users have to enter complex queries manually
and look up what information is stored in a set of relational tables. Without
a set of adequate information disclosure avenues an information system becomes
worthless since there is no use in storing information that will never be
retrieved.

An adequate support for information disclosure, however, is far from a trivial
problem. Most query languages and query mechanisms do not provide any support
for the users in their quest for information. Most of these existing
mechanisms can hardly be called disclosure mechanisms as they do not provide
users any support during the formulation process. Furthermore, the conceptual
schemata of real-life applications tend to be quite large and complicated. As
a result, users may easily become lost in conceptual space and they will end
up retrieving irrelevant (or even wrong) objects and may miss out on relevant
objects. Retrieving irrelevant objects leads to a low precision, missing
relevant objects has a negative impact on the recall ([SM83]).

The disclosure of information stored in an information system has some clear
parallels to the disclosure problems encountered in document retrieval
systems. To draw this parallel in more detail, we quote the information
retrieval paradigm as introduced in [BW92]. The paradigm starts with an
individual or company having an information need they wish to fulfil. This
need is typically a vague notion and needs to be made more concrete in terms
of an information request (the query) in some (formal) language. The
information request should be as good as possible a description of the
information need. The information request is then passed on to an automated
system, or a human intermediary, who will then try to fulfil the information
request using the information stored in the system. This is illustrated in the
information disclosure, or information retrieval paradigm, presented in
LABEL:Type.ov01irpd 1 which is taken from [BW92].

We now briefly discuss why the information retrieval paradigm for document
retrieval systems is also applicable for information systems. For a more
elaborate discussion on the relation between information systems and document
(information) retrieval systems in the context of the information retrieval
paradigm, refer to [Pro94a]. In the paradigm, the retrievable information is
modelled as a set ${\cal K}$ of information objects constituting the
information base (or population).

In a (multi-media) document retrieval system the information base will be a
set of multi-media documents ([SM83]), while in the case of an information
system the information base will contain a set of facts conforming to a
conceptual schema (although this could be multi-media as well). Each
information object $o\in\mbox{${\cal K}$}$ is characterised by a set of
descriptors $\mbox{${\cal X}$}(o)$ that facilitates its disclosure. The
characterisation of information objects is carried out by a process referred
to as indexing. In an information system, the stored objects (the population
or information base) can always be identified by a set of (denotable) values,
the identification of the object. For example, an address may be identified as
a city name, street name, and house number. The characterisation of objects in
an information system is directly provided by the reference schemes of the
object types.

The actual information disclosure is driven by a process referred to as
matching. In document retrieval applications this matching process tends to be
rather complex. The characterisation of documents is known to be a hard
problem ([Mar77], [Cra86]), although newly developed approaches turn out to be
quite successful ([Sal89]). In information systems the matching process is
less complex as the objects in the information base have a more clear
characterisation (the identification). In this case, the identification of the
objects (facts) is simply related to the query formulation $q$ by some
(formal) query language.

Figure 1: The information retrieval paradigm

The remaining problem is the query formulation process itself. An easy and
intuitive way to formulate queries is absolutely essential for an adequate
information disclosure. Quite often, the quest from users to fulfil their
information need can be aptly described by ([Bru93]):

> I don’t know what I’m looking for, but I’ll know when I find it.

In document retrieval systems this problem is attacked by using query by
navigation ([BW92], [Bru93]) and relevance feedback mechanisms ([Rij89]). The
query by navigation interaction mechanism between a searcher and the system is
well-known from the Information Retrieval field, and has proven to be useful.
It shall come as no surprise that these mechanisms also apply to the query
formulation problem for information systems. In [BPW93], [BPW94], [HPW94b],
[Pro94a] such applications of the query by navigation and relevance feedback
mechanisms have been described before. When combining the query by navigation
and manipulation mechanisms with the ideas behind visual interfaces for query
formulation as described in e.g. [ADD+92] and [Ros94], powerfull and intuitive
tools for computer supported query formulation become feasible, resulting in
improved information disclosure. Such tools will also heavily rely on the
ideas of direct manipulation interfaces ([Sch83]) as used in present day
computer interfaces.

One important step in the improvement of the information disclosure of
information systems, is the introduction of query languages on a conceptual
level. These languages allow for the formulation of queries in terms common to
the users, i.e. the verbalisations of the types in the conceptual schema.
Examples of such conceptual query languages are RIDL ([Mee82]), LISA-D
([HPW93], [HPW94a]), and FORML ([HHO92]). By letting users formulate queries
on a conceptual level, users are safeguarded from having to know the exact
mapping to internal representations (e.g. a set of tables which conform to the
relational model) to be able to formulate queries in a non conceptual language
such as SQL. The next step is to introduce ways to support users in the
formulation of queries in such conceptual query languages (CQL).

##  2 A New Generation of Formulation Mechanisms

In line with the above discussed information retrieval paradigm and the notion
of relevance feedback, a query formulation process (both for a document
retrieval system, and an information system) can be said to roughly consist of
the following four phases:

  1. 1.

The explorative phase. What information is there, and what does it mean?

  2. 2.

The constructive phase. Using the results of phase 1, the actual query is
formulated.

  3. 3.

The feedback phase. The result from the query formulated in phase 2 may not be
completely satisfactory. In this case, phases 1 and 2 need to be re-done and
the result refined.

  4. 4.

The presentation phase. In most cases, the result of a query needs to be
incorporated into a report or some other document. This means that the results
must be grouped or aggregated in some form.

Depending on the user’s knowledge of the system, the importance of the
respective phases may change. For instance, a user who has a good working
knowledge of the structure of the stored information may not require an
elaborate first phase and would like to proceed with the second phase as soon
as possible.

In the research for the InfoAssistant product, we try to integrate a palette
of complementary mechanisms to formulate queries on a conceptual level. These
mechanisms are the following:

query by navigation

This mechanism has been introduced in [BPW93], [PW95] and [Pro94a]. The idea
behind this mechanism is to shape a conceptual schema, which is essentially a
graph, as a hypertext and letting users formulate (part of) their information
need by navigating through this hypertext. This mechanisms is particularly
suited for those users who do not have a clear idea of what information is
stored in the information system as it is able to truely guide the user
through the (structure of the) stored information.

A precursor of the query by navigation mechanism for information systems
exists for information retrieval systems ([Bru93]). In expiriments it was
shown that in the IR case, this mechanism helps novice users in finding their
way around the stored information, without hampering expert users ([BBB91]).

All research that remains to be done in this area is some tuning and adapting
the existing (academic) ideas to the applied situation in InfoAssistant.

query by construction

This mechanism has also been discussed before in [BPW93], [PW95] and [Pro94a].
This mechanism was born out of the observation that the results of a query by
navigation sessions are relatively simple queries without advanced operations
such as grouping, intersections, counting, etc. Extending the query by
navigation mechanisms with such operations would have led to an unacceptable
increase in complexity. Therefore the introduction of the query by
construction as an additional mechanism was chosen.

The query by construction mechanism is basically a syntax directed editor
which allows a user to combine the query particles resulting from query by
navigation (and the three additional mechanisms discussed below) sessions to
be combined into complex queries using the more advanced operations.

Research-wise, this part is finished as there is not much research needed for
a syntax directed editor

point to point queries

The point to point queries originated from a rough idea from J. Harding. A
point to point query starts by selecting two or more object types from a
conceptual schema. Then the system should return a list of possible (non
cyclic) paths through the information structure between the specified object
types. For obvious reasons, the paths in this list should be ordered according
to some relevance criterion.

This style of querying corresponds to a situation in which users know some
aspects (object types) about which they want to be informed, but do not yet
know the exact details of their information need and the underlying
information structure. The query by navigation mechanism, on the other hand,
is intended to support users who do not have an overview of the stored
information.

In [Pro94b] this mechanism is discussed and formalised in full detail.

spider queries

This mechanism originated from a discussion with L. Delano. Users quite often
simply want to know all information about instances of an object type $x$. For
this purpose the spider queries were introduced. A crucial aspect of spider
queries is of course limiting the all information as users probably do not
want to be confronted with a listing of all information stored in the
information system.

The idea behind spider queries is to start out from one object type, and to
associate all information that is relevant to this object type. The essential
part of a spider query is selecting the object types in the direct suroundings
of the initial object type that are considered to be relevant, thus limiting
the amount of information returned to the user.

This style of querying corresponds to a situation where users only know about
the existance of some object types in the conceptual schema about which they
would like to be informed.

A complete discussion and formal treatment of this mechanism can be found in
[Pro94b].

natural language queries

A more commonly known mechanism for computer supported query formulation are
(semi) natural language query formulation systems. These mechanisms try to
interpret sentences in a semi-natural language format and generate an
appropriate query in SQL.

Our aim is to try and integrate these ideas with the newly added formulation
mechanisms. One important aspect of this integration is that it would allow us
to interpret the natural language sentence, and then automatically formulate a
query in a conceptual query language rather than SQL. This would certainly put
the user in a much better position to validate the resulting query than to
confront users with an SQL query.

A natural language formulation mechanism is usefull for those users who know
what information is stored in the information system, but who do not know the
exact names of the types. The flexibility of a semi-natural language would
then cater for this.

In the remainder of this overview report we discuss some example session using
the different disclosure avenues. This should give a more hands-on idea of
what these mechanisms are about.

##  3 An Example Session

In this section we discuss a sample session using the query formulation
component of InfoAssisant. The discussed example operates on a conceptual
schema for the administration of the election of American presidents. The
example schema itself is not shown; the structure of the domain will become
clear from the sample session. Note that the quality of the verbalisations of
paths expressions used in the examples in this section should be improved.
However, this is the subject of further research.

Figure 2: Building a PPQ query

In LABEL:Type.ov02pqst 2, a possible screen is depicted for building queries
using a point to point query mechanism. The upper window is concerned with the
point to point query itself, whereas the lower window contains the complete
query under construction. When specifying a point to point query a user
specifies a sequence of object types: the points. For each point, the user is
offered a listbox containing all object types present in the conceptual
schema. The order of the object types in the listbox should preferably be
based on some notion of conceptual importance ([CH94]). In LABEL:Type.ov02pqex
3 an existing point to point query path from president to election is extended
with another point.

Figure 3: Extending the PPQ path

Figure 4: Completing a PPQ

After all points of the point to point query have been specified, the point to
point query can be transformed into a proper query (i.e. a path through the
conceptual schema) by pressing the Go! button in the point to point query
window. In LABEL:Type.ov02pqcm 4, this process is illustrated. The sample PPQ
involves three points. Therefore, two paths through the conceptual schema will
result. We now shift our attention from the point to point query window to the
query by construction window. Note that the small box containing the PPQ
abbreviation is now replaced by the paths resulting from the point to point
query (i.e. President winning election which resulted in nr of votes). The
system initially inserts a most likely path. The user can, however, select
alternative paths using a listbox. Note that not all alternative paths between
the two points are listed in the listbox. The reason for this is the NP
completeness of the path searching problem. To avoid the NP completeness
problem, only the best paths are listed initially. However, potentially all
paths can be selected (which still remains NP complete) by repeatedly
selecting the MORE option. In the remainder of this article we will discuss
this in more detail.

Figure 5: Switching to query by navigation

Since every path resulting from a query by navigation session connects two
points in the conceptual schema, any path through the conceptual schema
displayed in the query by construction screen can be used as a starting point
for a query by navigation session, and vice versa. This is illustrated in
LABEL:Type.ov02pqnv 5. In this session, the user has selected the box which
contains the two paths politician is president of administration and
inaugurated in year for a query by navigation session. The upper window now
displays a node in the query by navigation session, with the path politician
is president of administration inaugurated in year as its focus. If the user
had selected the inaugurated in year listbox, the initial focus would have
been administration inaugurated in year.

The query by construction window in LABEL:Type.ov02pqnv 5 basically offers a
syntax directed editor. In the left part of the window all possible constructs
from the query language are listed. In our examples we have used the
constructs defined in LISA-D. Once the FORML and LISA-D languages have been
merged, a more complete language for the query by construction part will
result.

Figure 6: Start of a spider query

Next we discuss a session involving a spider query. We start out from an
existing query in a query by construction window, which could have been
constructed using a query by navigation querie or a point to point query. Note
that this could also be single object type, e.g. politician. The spider query
mechanism adds one important aspect to the query by construction window, the
spider button:  . When a user presses this button, the system calculates the
spider query of the object type directly to the right of the button. This is
illustrated in LABEL:Type.ov02sqrs 7. The system allows for the removal of
parts of the resulting spider query that are not considered to be relevant by
the user. Suppose the user is not interested in administration is headed by
and election won by, then these paths can be deleted, which leads to the
screen depicted in LABEL:Type.ov02sqpr 8.

Figure 7: Result of a Spider Query

Figure 8: Pruning the Spider Query

It is now interesting to see that a query essentially is a double tree with a
shared root (politician in the example). Furthermore, the leaves on the tree
resulting from the spider query can be extended further if desired by
commencing new spider queries. Finally, since the result of a spider query is
constructed from path expressions as well, these expressions have the
associated that can be used to select alternative paths between the head and
tail object types. Furthermore, the paths can also be used as a starting point
of a query by navigation session. This latter posibility is illustrated in
LABEL:Type.ov02sqbn 9.

Figure 9: Switching to query by navigation

asy

## References

  * [ADD+92] A. Auddino, Y. Dennebouy, Y. Dupont, E. Fontana, S. Spaccapietra, and Z. Tari.  SUPER – Visual Interaction with an Object–based ER Model.  In G. Pernul and A.M. Tjoa, editors, 11th International Conference on the Entity–Relationship Approach, volume 340-356 of Lecture Notes in Computer Science, pages 423–439, Berlin, Germany, EU, 1992\. Springer.
  * [BBB91] R. Bosman, R. Bouwman, and P.D. Bruza.  The Effectiveness of Navigable Information Disclosure Systems.  In G.A.M. Kempen, editor, Proceedings of the Informatiewetenschap 1991 conference, 1991.
  * [BPW93] C.A.J. Burgers, H.A. (Erik) Proper, and Th.P. van der Weide.  Organising an Information System as Stratified Hypermedia.  In H.A. Wijshoff, editor, Proceedings of the Computing Science in the Netherlands Conference, pages 109–120, November 1993.
  * [BPW94] C.A.J. Burgers, H.A. (Erik) Proper, and Th.P. van der Weide.  An Information System organized as Stratified Hypermedia.  In N. Prakash, editor, CISMOD94, International Conference on Information Systems and Management of Data, pages 159–183, October 1994.
  * [Bru93] P.D. Bruza.  Stratified Information Disclosure: A Synthesis between Information Retrieval and Hypermedia.  PhD thesis, University of Nijmegen, Nijmegen, The Netherlands, EU, 1993\.
  * [BW92] P.D. Bruza and Th.P. van der Weide.  Stratified Hypermedia Structures for Information Disclosure.  The Computer Journal, 35(3):208–220, 1992.
  * [CH94] L.J. Campbell and T.A. Halpin.  Abstraction Techniques for Conceptual Schemas.  In R. Sacks–Davis, editor, Proceedings of the 5th Australasian Database Conference, volume 16, pages 374–388, Christchurch, New Zealand, January 1994. Global Publications Services.
  * [Cra86] T.C. Craven.  String Indexing.  Academic Press, New York, New York, USA, 1986.
  * [HHO92] T.A. Halpin, J. Harding, and C-H. Oh.  Automated Support for Subtyping.  In B. Theodoulidis and A.G. Sutcliffe, editors, Proceedings of the Third Workshop on the Next Generation of CASE Tools, pages 99–113, May 1992.
  * [HPW93] A.H.M. ter Hofstede, H.A. (Erik) Proper, and Th.P. van der Weide.  Formal definition of a conceptual language for the description and manipulation of information models.  Information Systems, 18(7):489–523, October 1993.
  * [HPW94a] A.H.M. ter Hofstede, H.A. (Erik) Proper, and Th.P. van der Weide.  A Conceptual Language for the Description and Manipulation of Complex Information Models.  In G. Gupta, editor, Seventeenth Annual Computer Science Conference, volume 16 of Australian Computer Science Communications, pages 157–167, Christchurch, New Zealand, January 1994. University of Canterbury. ISBN 047302313
  * [HPW94b] A.H.M. ter Hofstede, H.A. (Erik) Proper, and Th.P. van der Weide.  Supporting Information Disclosure in an Evolving Environment.  In D. Karagiannis, editor, Proceedings of the 5th International Conference DEXA‘94 on Database and Expert Systems Applications, Athens, Greece, EU, volume 856 of Lecture Notes in Computer Science, pages 433–444, Berlin, Germany, EU, September 1994. Springer. ISBN 3540584358
  * [Mar77] M.E. Maron.  On Indexing, Retrieval and the Meaning of About.  Journal of the American Society for Information Science, 28(1):38–43, 1977.
  * [Mee82] R. Meersman.  The RIDL Conceptual Language.  Technical report, International Centre for Information Analysis Services, Control Data Belgium, Inc., Brussels, Belgium, EU, 1982.
  * [Pro94a] H.A. (Erik) Proper.  A Theory for Conceptual Modelling of Evolving Application Domains.  PhD thesis, University of Nijmegen, Nijmegen, The Netherlands, EU, 1994\. ISBN 909006849X
  * [Pro94b] H.A. (Erik) Proper.  Interactive Query Formulation using Point to Point Queries.  Technical report, Asymetrix Research Laboratory, University of Queensland, Brisbane, Queensland, Australia, 1994.
  * [PW95] H.A. (Erik) Proper and Th.P. van der Weide.  Information Disclosure in Evolving Information Systems: Taking a shot at a moving target.  Data & Knowledge Engineering, 15:135–168, 1995.
  * [Rij89] C.J. van Rijsbergen.  Towards an information logic.  In Proceedings of the 12th annual international ACM SIGIR conference on Research and development in information retrieval, Cambridge, Massachusetts, USA, pages 77–86, New York, New York, USA, June 1989. ACM.
  * [Ros94] P. Rosengren.  Using Visual ER Query Systems in Real World Applications.  In G.M. Wijers, S. Brinkkemper, and T. Wasserman, editors, Proceedings of the Sixth International Conference CAiSE‘94 on Advanced Information Systems Engineering, Utrecht, The Netherlands, EU, volume 811 of Lecture Notes in Computer Science, pages 394–405, Berlin, Germany, EU, June 1994. Springer.
  * [Sal89] G.E Salton.  Automatic Text Processing–The Transformation, Analysis, and Retrieval of Information by Computer.  Addison Wesley, Reading, Massachusetts, USA, 1989.
  * [Sch83] B. Schneiderman.  Direct Manipulation: A Step Beyond Programming Languages.  IEEE Computer, 16(8):57–69, 1983.
  * [SM83] G.E Salton and M.J. McGill.  Introduction to Modern Information Retrieval.  McGraw–Hill, New York, New York, USA, 1983.