# On short edges in complete topological graphs

Andrew Suk Department of Mathematics, University of California at San Diego,
La Jolla, CA, 92093 USA. Supported by NSF CAREER award DMS-1800746 and NSF
award DMS-1952786. Email<EMAIL_ADDRESS>
###### Abstract

Let $h(n)$ be the minimum integer such that every complete $n$-vertex simple
topological graph contains an edge that crosses at most $h(n)$ other edges. In
2009, Kynčl and Valtr showed that $h(n)=O(n^{2}/\log^{1/4}n)$, and in the
other direction, gave constructions showing that $h(n)=\Omega(n^{3/2})$. In
this paper, we prove that $h(n)=O(n^{7/4})$. Along the way, we establish a new
variant of Chazelle and Welzl’s matching theorem for set systems with bounded
VC-dimension, which we believe to be of independent interest.

##  1 Introduction

A _topological graph_ is a graph drawn in the plane such that its vertices are
represented by points and its edges are represented by non-self-intersecting
arcs connecting the corresponding points. The edges are allowed to intersect,
but they may not intersect vertices except for their endpoints. Furthermore,
no two edges are tangent, i.e., if two edges share an interior point in
common, then they must properly cross at that point in common. Two edges of a
topological graph _cross_ if their interiors share a point, and are _disjoint_
if they have no points in common. A topological graph is _simple_ if every
pair of its edges intersect at most once, either at a common endpoint or at a
proper crossing point. If the edges are drawn as straight-line segments, then
the graph is said to be _geometric_. If the vertices of a geometric graph are
in convex position, then it is called _convex_. Finally, given a complete
$n$-vertex topological graph $G$, we say that an edge in $G$ is _short_ if at
most $o(n^{2})$ other edges cross it.

It is easy to see that there are many complete topological graphs with no
short edges. Moreover, Pach and Tóth [12] showed that, for every $n\geq 2$,
there are complete $n$-vertex topological graphs with the property that every
pair of edges has exactly one or two points in common, and hence, has no short
edges. However, the situation changes for _simple_ topological graphs. Let
$h(n)$ be the minimum integer such that every complete $n$-vertex simple
topological graph contains an edge that crosses at most $h(n)$ other edges. In
2003, Brass, Moser, and Pach [3] conjectured that one can always find a short
edge in a complete simple toplogical graph, that is, $h(n)=o(n^{2})$. The best
known lower bound at the time was $h(n)=\Omega(n)$, due to a result of
Harborth and Thürmann [8] from 1994. Their conjecture was verified by Kynčl
and Valtr [10] in 2009, who showed that

$\Omega\left(n^{3/2}\right)\leq h(n)\leq
O\left(\frac{n^{2}}{\log^{1/4}n}\right).$

See also [18] for a slightly better upper bound. Our main result is the first
polynomial improvement in the upper bound for $h(n)$.

######  Theorem 1.1.

For $n\geq 2$, we have $h(n)=O\left(n^{7/4}\right)$.

Our paper is organized as follows. In the next section, we recall the notion
of VC-dimension and prove a result on matchings with low stabbing number in
set systems with bounded VC-dimension. In Section 3, we use this matching
result to prove Theorem 1.1. We conclude the paper with several remarks and
open problems. For sake of clarity, we omit floor and ceiling signs whenever
they are not crucial.

##  2 VC-dimension and the dual shatter function

Given a set-system $\mathcal{F}$ with a ground set $V$, the _Vapnik-
Chervonenkis dimension_ (in short, VC-dimension) of $\mathcal{F}$ is the
largest integer $d$ for which there exists a $d$-element set $X\subset V$ such
that for every subset $Y\subset X$, one can find a member $A\in\mathcal{F}$
with $A\cap X=Y$. The VC-dimension, introduced by Vapnik and Chervonenkis
[19], is one of the most useful combinatorial parameters that measures the
complexity of a set system, with a wide range of applications in statistics,
logic, learning theory, graph drawing, and computational geometry. Throughout
this paper, all set systems will be _multisets_ , that is, $\mathcal{F}$ may
contain several copies of the same set $A\in\mathcal{F}$. The cardinality of
$\mathcal{F}$, denoted by $|\mathcal{F}|$, is counted with these
multiplicities.

Here, it will be more convenient to work with the dual VC-dimension and the
dual shatter function of $\mathcal{F}$. The _dual shatter function_ of
$\mathcal{F}$, denoted by $\pi_{\mathcal{F}}^{\ast}(m)$, is the maximum number
of nonempty cells of the Venn diagram of $m$ sets in $\mathcal{F}$. In other
words, $\pi_{\mathcal{F}}^{\ast}(m)$ is the maximum number of equivalence
classes on $V$ defined by an $m$-element subfamily
$\mathcal{S}\subset\mathcal{F}$, where two points $x,y\in V$ are equivalent
with respect to $\mathcal{S}$ if $x$ belongs to the same sets of $\mathcal{S}$
as $y$ does. The _dual VC-dimension_ of $\mathcal{F}$ is the maximum possible
number of sets in $\mathcal{F}$ with a complete Venn diagram, that is, the
maximum $d^{\ast}$ such that
$\pi^{\ast}_{\mathcal{F}}(d^{\ast})=2^{d^{\ast}}$. The classical theorem of
Sauer [15] and Shelah [16] implies that if $\mathcal{F}$ has dual VC-dimension
$d^{\ast}$, then
$\pi^{\ast}_{\mathcal{F}}(m)\leq\sum_{i=0}^{d^{\ast}}\binom{m}{i}$. Moreover,
it is know that $d^{\ast}\leq 2^{d}$ if $\mathcal{F}$ has VC-dimension $d$
(see [4]).

Let $\mathcal{F}$ be a set system with ground set $V$. Given two points
$u,v\in V$, we say that a set $A\in\mathcal{F}$ _stabs_ the pair $\\{u,v\\}$
if $A$ contains exactly one element of $\\{u,v\\}$. We say that the subset
$X\subset V$ is _$\delta$ -separated_ if for any two points $u,v\in X$, there
are at least $\delta$ sets in $\mathcal{F}$ that stabs the pair $\\{u,v\\}$.
In 1995, Haussler proved the following interesting theorem.

######  Lemma 2.1 ([9]).

Let $\mathcal{F}$ be a set system on a ground set $V$ with
$\pi^{\ast}_{\mathcal{F}}(m)=cm^{d}$. If $X\subset V$ is $\delta$-separated,
then $|X|\leq c_{1}(|\mathcal{F}|/\delta)^{d}$ where $c_{1}=c^{\prime}(d,c)$.

As an application of Lemma 2.1, Fox, Pach, and the author [6] showed the
following.

######  Lemma 2.2 ([6]).

Let $\mathcal{F}$ be a set system on a ground set $V$ such that $|V|=n$ and
$\pi^{\ast}_{\mathcal{F}}(m)=cm^{d}$. Then there is a constant
$c_{2}=c_{2}(d,c)>1$ such that for any $\delta$ satisfying
$1\leq\delta\leq|\mathcal{F}|$, there is a partition $V=S_{1}\cup\cdots\cup
S_{r}$ of $V$ into $r\leq c_{2}(|\mathcal{F}|/\delta)^{d}$ parts, such that
any pair of vertices from the same part $S_{i}$ is stabbed by at most
$2\delta$ members of $\mathcal{F}$.

Together with the pigeonhole principle, Lemma 2.2 implies the following.

######  Corollary 2.3 ([6]).

Let $\mathcal{F}$ be a set system on a ground set $V$ such that $|V|=n$ and
$\pi^{\ast}_{\mathcal{F}}(m)=cm^{d}$. Then there is a constant
$c_{2}=c_{2}(d,c)$ such that for any $\delta$ satisfying
$1\leq\delta\leq|\mathcal{F}|$, there is a subset $U\subset V$ such that
$|U|\geq\frac{n}{c_{2}(|\mathcal{F}|/\delta)^{d}}$, and any pair of vertices
in $U$ is stabbed by at most $2\delta$ members of $\mathcal{F}$.

In [4], Chazelle and Welzl proved that if $\mathcal{F}$ is a set system with
ground set $V$, such that $|V|=n$, $n$ is even, and
$\pi^{\ast}_{\mathcal{F}}(m)=O(m^{d})$, then there is a perfect matching $M$
on $V$ with the property that for any set $A\in\mathcal{F}$, $A$ stabs at most
$O(n^{1-1/d})$ matchings in $M$. One of the main tools we will need for the
proof of Theorem 1.1 is the following variant of Chazelle and Welzl’s matching
theorem, which we believe to be of independent interest.

######  Lemma 2.4.

Let $\mathcal{F}$ be a set system on a ground set $V=\\{v_{1},\ldots,v_{n}\\}$
such that $\pi^{\ast}_{\mathcal{F}}(m)\leq cm^{d}$ and $|\mathcal{F}|\leq
cn^{d}$, where $d\geq 2$. Then there is a subset $X\subset V$ such that
$|X|\leq 2n^{1/2+1/(2d)}$, a constant $c_{3}=c_{3}(d,c)$, and a perfect
matching $M$ on $V\setminus X$, such that the following properties holds.

  1. 1.

For each $\\{v_{i},v_{j}\\}\in M$, $|i-j|\leq n^{1-1/(2d)}$.

  2. 2.

For each $\\{v_{i},v_{j}\\}\in M$, at most $c_{3}(|\mathcal{F}|/n^{1/(2d)})$
sets in $\mathcal{F}$ stabs $\\{v_{i},v_{j}\\}$.

  3. 3.

For each set $A\in\mathcal{F}$, $A$ stabs at most $c_{3}n^{1-1/d}$ members of
$M$.

###### Proof.

Let $\mathcal{F}$ be a set system with ground set $V$ such that
$\pi^{\ast}_{\mathcal{F}}(m)=cm^{d}$, and let $c_{3}=c_{3}(d,c)$ be a large
constant that will be determined later. We apply Lemma 2.2 to $\mathcal{F}$
with parameter $\delta=c_{2}\left(\frac{|\mathcal{F}|}{n^{1/(2d)}}\right)$,
where $c_{2}>1$ is defined in Lemma 2.2, to get a partition on $V$,

$\mathcal{P}:V=P_{1}\cup P_{2}\cup\cdots\cup P_{r},$

such that $r<n^{1/2}$ and with the properties described in Lemma 2.2. We
further partition each part $P_{k}$ into at most $n^{1/(2d)}$ smaller parts,
such that two vertices $v_{i},v_{j}$ from a resulting part satisfies
$|i-j|\leq n^{1-1/(2d)}$. Let

$\mathcal{P}^{\prime}:V=S_{1}\cup S_{2}\cup\cdots\cup S_{t},$

the be resulting partition, where $t<n^{1/2+1/(2d)}$. Hence, for any two
vertices $v_{i},v_{j}\in S_{k}$ in the same part, at most
$2\delta=2c_{2}\left(\frac{|\mathcal{F}|}{n^{1/(2d)}}\right)$ sets in
$\mathcal{F}$ stabs $\\{v_{i},v_{j}\\}$, and we have $|i-j|\leq n^{1-1/(2d)}.$

In what follows, we construct our matching $M$ by picking the pairs
$\\{x_{i},y_{i}\\}$ one by one, such that for each pair $\\{x_{i},y_{i}\\}\in
M$, both $x_{i}$ and $y_{i}$ lie in the same part of $\mathcal{P}^{\prime}$.
By setting $c_{3}$ sufficiently large, this will guarantee that the first two
properties of the lemma to hold for $M$. In order to achieve the third
property, we apply a well-known iterative reweighting strategy (see also [4,
11]).

Suppose we have obtained pairs
$M_{i}=\\{\\{x_{1},y_{1}\\},\\{x_{2},y_{2}\\},\ldots,\\{x_{i},y_{i}\\}\\}$ for
our matching, where $i\leq n/2-n^{1/2+1/(2d)}$. We define the weight
$w_{i}(A)$ of a set $A\in\mathcal{F}$ as $2^{\kappa_{i}(A)}$, where
$\kappa_{i}(A)$ is the number of matchings in $M_{i}$ that is stabbed by
$A\in\mathcal{F}$. Let $V_{i}=V\setminus\\{x_{1},y_{1},\ldots,x_{i},y_{i}\\},$
and let $\mathcal{F}_{i}$ be a set system with ground set $V_{i}$, where we
add the set $A\cap V_{i}$ to $\mathcal{F}_{i}$ with multiplicity $w_{i}(A)$.
Thus, $w_{0}(A)=1$ for all $A\in\mathcal{F}$, and we have $V_{0}=V$ and
$\mathcal{F}_{0}=\mathcal{F}$.

We select $\\{x_{i+1},y_{i+1}\\}$ in $V_{i}$ as follows. Since
$\pi^{\ast}_{\mathcal{F}_{i}}(m)\leq cm^{d}$, we apply Corollary 2.3 to
$\mathcal{F}_{i}$ with parameter
$\delta=c_{2}\frac{|\mathcal{F}|}{(n-2i)^{1/d}}$, where $c_{2}>1$ is defined
in Lemma 2.2, to obtain a subset $U_{i}\subset V_{i}$ such that
$|U_{i}|\geq(n-2i)$, and each pair of vertices in $U_{i}$ is stabbed by at
most $2\delta=2c_{2}\frac{|\mathcal{F}_{i}|}{(n-2i)^{1/d}}$ sets in
$\mathcal{F}_{i}$. Since $i\leq n/2-n^{1/2+1/(2d)}$, we have

$|U_{i}|\geq(n-2i)\geq 2n^{1/2+1/(2d)}>t.$

By the pigeonhole principle, two vertices of $U_{i}$ must lie in the same part
of the partition $\mathcal{P}^{\prime}$. Let $x_{i+1},y_{i+1}$ be two such
vertices and set $M_{i+1}=M_{i}\cup\\{x_{i+1},y_{i+1}\\}$ and
$V_{i+1}=V_{i}\setminus\\{x_{i+1},y_{i+1}\\}$. Therefore, we have

$|\mathcal{F}_{i+1}|\leq|\mathcal{F}_{i}|+2c_{2}\frac{|\mathcal{F}_{i}|}{(n-2i)^{1/d}}=|\mathcal{F}_{i}|\left(1+\frac{2c_{2}}{(n-2i)^{1/d}}\right).$

We repeat this process until we have obtained a matching $M$ of size
$w=\lfloor n/2-n^{1/2+1/(2d)}\rfloor$. At this point, we stop and set $X$ to
be the remaining vertices $V\setminus\\{x_{1},y_{1},\ldots,x_{w},y_{w}\\}$.
Therefore, we have $|X|\leq 2n^{1/2+1/(2d)}$ and

$\displaystyle|\mathcal{F}_{w}|$
$\displaystyle\leq\prod\limits_{i=0}^{w-1}|\mathcal{F}|\left(1+\frac{2c_{2}}{(n-2i)^{1/d}}\right)$
$\displaystyle\leq|\mathcal{F}|e^{\sum_{i=0}^{w-1}\frac{2c_{2}}{(n-2i)^{1/d}}}$
$\displaystyle\leq|\mathcal{F}|e^{4c_{2}n^{1-1/d}}$ $\displaystyle\leq
e^{4c_{2}n^{1-1/d}+\ln(|\mathcal{F}|)}$ $\displaystyle\leq
e^{8c_{2}n^{1-1/d}}.$

The last inequality follows from the fact that $|\mathcal{F}|\leq cn^{d}$. For
any set $A\in\mathcal{F}$, if $A$ stabs $\kappa$ members in $M$, then we have
$2^{\kappa}\leq e^{8c_{2}n^{1-1/d}}$, which implies that $\kappa\leq
c_{3}n^{1-1/d}$ for $c_{3}$ sufficiently large. ∎

##  3 Proof of Theorem 1.1

Let $G=(U,E)$ be a complete simple topological graph with $n+1$ vertices.
Given a subset $S\subset U$, we denote by $G[S]$ the topological subgraph of
$G$ induced by the vertex set $S$. For simplicity, we write $G[u,v]=uv$. In
order to avoid confusion between topological edges and pairs of vertices, we
write $uv$ when referring to the topological edge in the plane, and write
$\\{u,v\\}$ when referring to the pair. By the simple condition, all 3-cycles
in $G$ are non-self-intersecting, and we will sometimes refer to them as
_triangles_ in $G$. Also for convenience, say that a vertex $z$ lies _inside_
the triangle $T=G[u,v,w]$, if $z$ lies in the bounded region enclosed by
$G[u,v,w]$. Moreover, we say that the edge $xy\in E(G)$ lies _inside_ of
triangle $G[u,v,w]$ if $x$ and $y$ lie inside $G[u,v,w]$, and $xy$ does not
cross $G[u,v,w]$. See Figure 1(a).

Notice that the edges of $G$ divide the plane into several cells (regions),
one of which is unbounded. We can assume that there is a vertex $v_{0}\in U$
such that $v_{0}$ lies on the boundary of the unbounded cell. Indeed,
otherwise we can project $G$ onto a sphere, then choose an arbitrary vertex
$v_{0}$ and then project $G$ back to the plane such that $v_{0}$ lies on the
boundary of the unbounded cell, and moreover two edges cross in the new
drawing if and only if they crossed in the original drawing.

Consider the topological edges emanating out from $v_{0}$, and label their
endpoints $v_{1},\dots,v_{n}$ in counter-clockwise order. Thus, for $i<j$, the
sequence $(v_{0},v_{i},v_{j})$ appears in counter-clockwise order along the
non-self-intersecting 3-cycle $G[v_{0},v_{i},v_{j}]$. Set $V=U\setminus
v_{0}$. For $1\leq i<j\leq n$, let $I_{i,j}=\\{v_{k}\in V:i<k<j\\}$.

We define the set system $\mathcal{F}$ with ground set $V$ as follows. For
each pair $v_{i},v_{j}\in V$ with $i<j$, we define the set $T_{i,j}$ to be the
set of vertices in $V$ that lie inside the triangle $G[v_{0},v_{i},v_{j}]$.
See Figure 1(b) for a small example. Then set

(a) Edge $xy$ inside triangle $G[u,v,w]$.

(b) $T_{3,6}=\\{v_{1},v_{4}\\}$.

Figure 1: Triangles in $G$.

$\mathcal{F}=\\{T_{i,j}:1\leq i<j\leq n\\}.$

In [17], the author proved the following lemma, and for sake of completeness,
we include its short proof here.

######  Lemma 3.1 ([17]).

Let $\mathcal{F}$ be the set system with ground set $V$ defined as above. Then
$\pi^{*}_{\mathcal{F}}(m)\leq 5m^{2}$.

###### Proof.

In order to obtain an upper bound on $\pi^{*}_{\mathcal{F}}(m)$, we simply
need to bound the maximum number of regions for which $m$ triangles in $G$
partitions the plane into. We proceed by induction on $m$. The base case when
$m=1$ is trivial. Now assume that the statement holds up to $m-1$. Notice that
any set of $m-1$ triangles consists of at most $3(m-1)$ topological edges of
$G$. Therefore, when we add the $m$th triangle $T=G[v_{0},v_{i},v_{j}]$, each
topological edge in $T$ creates at most $3(m-1)$ new crossing points since $G$
is simple. Hence, triangle $T$ creates at most $9(m-1)$ new regions in the
arrangement. By the induction hypothesis, we have at most

$5(m-1)^{2}+9(m-1)\leq 5m^{2}$

cells created by the $m$ triangles.∎

Since the set system $\mathcal{F}$ satisfies $\pi^{\ast}_{\mathcal{F}}(m)\leq
5m^{2}$ and $|\mathcal{F}|\leq n^{2}/2$, we can apply Lemma 2.4 to
$\mathcal{F}$ to obtain a subset $X\subset V$ such that $|X|\leq 2n^{3/4}$, a
perfect matching $M_{1}$ on $V\setminus X$, and an absolute constant $c_{3}$
such that the following holds.

  1. 1.

For each $\\{v_{i},v_{j}\\}\in M_{1}$, $|i-j|\leq n^{3/4}$.

  2. 2.

For each $\\{v_{i},v_{j}\\}\in M_{1}$, at most $c_{3}(|\mathcal{F}|/n^{1/4})$
sets in $\mathcal{F}$ stabs $\\{v_{i},v_{j}\\}$.

  3. 3.

For each set $A\in\mathcal{F}$, $A$ stabs at most $c_{3}n^{1/2}$ members of
$M_{1}$.

Let $\Gamma_{1}$ be a directed auxiliary graph such that
$V(\Gamma_{1})=M_{1}$, and for $\\{v_{i},v_{j}\\},\\{v_{k},v_{\ell}\\}\in
V(\Gamma_{1})$, we have a directed edge from $\\{v_{i},v_{j}\\}$ to
$\\{v_{k},v_{\ell}\\}$ if and only if $T_{i,j}$ stabs the pair
$\\{v_{k},v_{\ell}\\}$. By the third property above, $\Gamma_{1}$ has at most
$|M_{1}|c_{3}n^{1/2}\leq c_{3}n^{3/2}$ directed edges, and therefore, the sum
of the in-degree of each vertex in $\Gamma_{1}$ is at most $c_{3}n^{3/2}$.
Hence, the number of vertices in $\Gamma_{1}$ whose in-degree at least
$n^{3/4}$ is at most

$\frac{c_{3}n^{3/2}}{n^{3/4}}=c_{3}n^{3/4}.$

Let $M_{2}\subset M_{1}$ be the members in $M_{1}$ whose in-degree is less
than $n^{3/4}$ in $\Gamma_{1}$. Hence, $|M_{1}\setminus M_{2}|\leq
c_{3}n^{3/4}$, and

$|M_{2}|\geq\frac{n}{2}-n^{3/4}-c_{3}n^{3/4}.$

For integers $1\leq i<j\leq n$, let $\phi_{M_{2}}(v_{i},v_{j})$ denote the
number of matchings $\\{v_{k},v_{\ell}\\}\in M_{2}$ such that both
$v_{k},v_{\ell}$ lie inside triangle $G[v_{0},v_{i},v_{j}]$. Set
$\\{v_{x},v_{y}\\}\in M_{2}$ to be the matching such that
$\phi_{M_{2}}(v_{x},v_{y})\leq\phi_{M_{2}}(v_{i},v_{j})$, for any
$\\{v_{i},v_{j}\\}\in M_{2}$. We now make the following claim.

######  Claim 3.2.

The topological edge $v_{x}v_{y}$ crosses at most $c_{4}n^{7/4}$ other edges
in $G$, where $c_{4}$ is a sufficiently large absolute constant.

###### Proof.

We define subsets $E_{0},E_{1},E_{2},E_{3},E_{4}\subset E(G)$ as follows. Let
$E_{0}$ be the edges in $G$ incident to $v_{0}$. Let $E_{1}\subset E(G)$ be
the set of edges in $G$ that has an endpoint in $X$. Let $E_{2}$ be the set of
edges $v_{i}v_{j}$ in $G$ with an endpoint in $I_{x,y}=\\{v_{k}\in
V:x<k<y\\}$. Let $E_{3}$ be the set of edges $v_{i}v_{j}$ such that
$v_{i}v_{j}$ crosses $v_{x}v_{y}$, and the set $T_{i,j}$ stabs the pair
$\\{v_{x},v_{y}\\}$. Let $E_{4}$ be the set of edges $v_{i}v_{j}$ that crosses
$v_{x}v_{y}$, such that $v_{i}v_{j}$ is not in $E_{0},E_{1}$, $E_{2}$, nor
$E_{3}$. It is easy to see that for any edge $v_{i}v_{j}\in E(G)$ that crosses
$v_{x}v_{y}$, we have $v_{i}v_{j}\in E_{0}\cup E_{1}\cup\cdots\cup E_{4}$.

Clearly, we have

$|E_{0}|\leq n.$ (1)

Since $|X|\leq 2n^{3/4}$, we have

$|E_{1}|\leq 2n^{7/4}.$ (2)

By the first property of our matching, we have $|x-y|<n^{3/4}$. Therefore, we
have

$|E_{2}|\leq n^{7/4}.$ (3)

Since $\\{v_{x},v_{y}\\}\in M_{2}$, at most $c_{3}|\mathcal{F}|/n^{1/4}\leq
c_{3}n^{7/4}$ sets in $\mathcal{F}$ stabs $\\{v_{x},v_{y}\\}$. Hence, we have

$|E_{3}|\leq c_{3}n^{7/4}.$ (4)

(a) $x<y<i<j$.

(b) $i<x<y<j$.

(c) $i<x<y<j$.

(d) $x<y<i<j$.

Figure 2: Observation 3.3 with $v_{i},v_{j}\in U_{1}$ or $v_{i},v_{j}\in
U_{2}$.

Thus, it remains to bound $|E_{4}|$. Let

$U_{1}=\\{v_{k}\in V\setminus I_{x,y}:v_{0}v_{k}\textnormal{ crosses
}v_{x}v_{y}\\}$

and

$U_{2}=\\{v_{k}\in V\setminus I_{x,y}:v_{0}v_{k}\textnormal{ is disjoint to
}v_{x}v_{y}\\}.$

We now make the following observation.

######  Observation 3.3.

If $v_{i}v_{j}\in E_{4}$, then $v_{i}v_{j}$ has one endpoint in $U_{1}$ and
the other in $U_{2}$.

###### Proof.

For sake of contradiction, suppose that $v_{i},v_{j}\in U_{2}$ such that
$i<j$. Since $v_{i}v_{j}$ crosses $v_{x}v_{y}$, and since $G$ is simple,
$v_{i}v_{j}$ must cross either $v_{0}v_{x}$ or $v_{0}v_{y}$, but not both.
Without loss of generality, we can assume that $v_{i}v_{j}$ crosses
$v_{0}v_{y}$. Since $v_{i}v_{j}\in E_{4}$, we have that $v_{i},v_{j}\not\in
I_{x,y}$. Hence, if we have $i<j<x$ or $y<i<j$, then the set $T_{i,j}$
contains $v_{y}$ but not $v_{x}$. Therefore, $T_{i,j}$ stabs
$\\{v_{i},v_{j}\\}$, and we have $v_{i}v_{j}\not\in E_{4}$ which is a
contradiction. See Figure 2(a). If we have $i<x<y<j$, then the set $T_{i,j}$
contains $v_{x}$ but not $v_{y}$. See Figure 2(b). Hence, $T_{i,j}$ stabs
$\\{v_{x},v_{y}\\}$ which implies that $v_{i}v_{j}\not\in E_{4}$,
contradiction. A symmetric argument follows if $v_{i},v_{j}\in U_{1}$. See
Figures 2(c) and 2(d). ∎

For sake of contradiction, let us suppose that $|E_{4}|>(c_{4}/2)n^{7/4}$,
where $c_{4}$ is a large constant that will be determined later. Since
$|U_{2}|\leq n$, the observation above implies that
$|U_{1}|>(c_{4}/2)n^{3/4}.$ In what follows, we will find another matching
$\\{v_{x^{\prime}},v_{y^{\prime}}\\}\in M_{2}$ such that
$\phi_{M_{2}}(v_{x^{\prime}},v_{y^{\prime}})<\phi_{M_{2}}(v_{x},v_{y})$, which
will be our contradiction.

######  Claim 3.4.

There is a subset $M_{4}\subset M_{2}$, where

$|M_{4}|\geq\frac{c_{4}n^{3/4}}{16},$

such that for each matching $\\{v_{i},v_{j}\\}\in M_{4}$, we have
$v_{i},v_{j}\in U_{1}$ and the topological edge $v_{i}v_{j}$ lies completely
inside of triangle $G=[v_{0},v_{x},v_{y}]$.

###### Proof.

Let $S_{1},\ldots,S_{4}\subset U_{1}$, such that $S_{1}=U_{1}\cap X$,

$S_{2}=\\{v_{i}\in U_{1}:\\{v_{i},v_{j}\\}\in M_{1}\setminus M_{2}\\},$

$S_{3}=\\{v_{i}\in U_{1}:\\{v_{i},v_{j}\\}\in M_{2},v_{j}\in I_{x,y}\\},$

$S_{4}=\\{v_{i}\in U_{1}:\\{v_{i},v_{j}\\}\in M_{2},v_{j}\in U_{2}\\}.$

Clearly we have $|S_{1}|\leq 2n^{3/4}$ since $|X|\leq 2n^{3/4}$. Moreover, at
most $2|M_{1}\setminus M_{2}|\leq 2c_{3}n^{3/4}$ vertices in $U_{1}$ are
endpoints of a matching in $M_{1}$ but not in $M_{2}$. Thus $|S_{2}|\leq
2c_{3}n^{3/4}$. Since $|I_{x,y}|\leq n^{3/4}$, we have $|S_{3}|\leq n^{3/4}$.
Finally, if $v_{i}\in U_{1}$ and $v_{j}\in U_{2}$, the set $T_{x,y}$ stabs
$\\{v_{i},v_{j}\\}.$ By the third property of the matching $M_{1}$, we have
$|S_{4}|\leq c_{3}n^{1/2}.$

Let $S_{5}=U_{1}\setminus(S_{1}\cup\cdots\cup S_{4})$. By setting $c_{4}$
sufficiently large, we have

$\displaystyle|S_{5}|$
$\displaystyle\geq|U_{1}|-2n^{3/4}-2c_{3}n^{3/4}-n^{3/4}-c_{3}n^{1/2}$
$\displaystyle\geq(c_{4}/4)n^{3/4}.$

Thus, we have a perfect matching $M_{3}$ on $S_{5}$ such that $M_{3}\subset
M_{2}$. Finally, let us count the number of matchings $\\{v_{i},v_{j}\\}\in
M_{3}\subset M_{1}$ such that the topological edge $v_{i}v_{j}$ does lie
completely inside triangle $G[v_{0},v_{x},v_{y}]$. If $\\{v_{i},v_{j}\\}\in
M_{3}$ and $v_{i}v_{j}$ does not lie completely inside of
$G[v_{0},v_{x},v_{y}]$, then $v_{i}v_{j}$ must cross exactly two edges of the
triangle $G[v_{0},v_{x},v_{y}]$. Moreover, the two edges cannot be
$v_{0}v_{x}$ and $v_{0}v_{y}$. See Figures 3(a) and 3(b). Hence, $v_{i}v_{j}$
must then cross $v_{x}v_{y}$. As argued in Observation 3.3, the set $T_{i,j}$
stabs $\\{v_{x},v_{y}\\}$. Since the in-degree of $\\{v_{x},v_{y}\\}\in M_{2}$
is less than $n^{3/4}$ in the directed graph $\Gamma_{1}$, there are at most
$n^{3/4}$ such matchings. We delete these matchings, leaving us with a
matching $M_{4}\subset M_{3}$, where

(a) $x<y<i<j$.

(b) $i<x<y<j$.

Figure 3: Edge $v_{i}v_{j}$ violating the simple condition by crossing both
$v_{0}v_{x}$ and $v_{0}v_{y}$.

$\displaystyle|M_{4}|$ $\displaystyle\geq\frac{|S_{5}|}{2}-n^{3/4}$
$\displaystyle\geq(c_{4}/8)n^{3/4}-n^{3/4}$
$\displaystyle\geq(c_{4}/16)n^{3/4},$

such that for each $\\{v_{i},v_{j}\\}\in M_{4}$, $v_{i},v_{j}\in U_{1}$, and
the topological edge $v_{i}v_{j}$ lies completely inside of triangle
$G[v_{0},v_{x},v_{y}]$. ∎

Fix a matching $\\{v_{i},v_{j}\\}\in M_{4}$. Then notice that for any vertex
$v_{k}\in U_{1}$ such that $v_{k}\not\in I_{x,y}\cup I_{i,j}$, if $v_{k}$ lies
inside of triangle $G[v_{0},v_{i},v_{j}]$, then $v_{k}$ lies inside of
triangle $G[v_{0},v_{x},v_{y}]$. See Figure 4(a). We create a second auxiliary
directed graph $\Gamma_{4}$, where $V(\Gamma_{4})=M_{4}$, and we have a
directed edge from $\\{v_{k},v_{\ell}\\}$ to $\\{v_{i},v_{j}\\}$ if and only
if $v_{k}$ and $v_{\ell}$ lie inside of triangle $G[v_{0},v_{i},v_{j}]$.

######  Observation 3.5.

Let $\\{v_{i},v_{j}\\},\\{v_{k},v_{\ell}\\}\in V(\Gamma_{4})$. Suppose
$v_{i},v_{j}\not\in I_{k,\ell}$ and $v_{k},v_{\ell}\not\in I_{i,j}$. Then
there is at most one directed edge between $\\{v_{i},v_{j}\\}$ and
$\\{v_{i},v_{\ell}\\}$ in $\Gamma_{4}$.

###### Proof.

Without loss of generality, we can assume $i<j<k<\ell$. For sake of
contradiction, suppose we have two directed edges (both directions) between
$\\{v_{i},v_{j}\\}$ and $\\{v_{i},v_{\ell}\\}$ in $\Gamma_{4}$. Hence,
$v_{k},v_{\ell}$ both lie inside of triangle $G[v_{0},v_{i},v_{j}]$. If the
edge $v_{k}v_{\ell}$ lies inside of $G[v_{0},v_{i},v_{j}]$, then we only have
one directed edge between between $\\{v_{i},v_{j}\\}$ and
$\\{v_{i},v_{\ell}\\}$ in $\Gamma_{4}$, which is a contradiction. Therefore,
we can assume that $v_{k}v_{\ell}$ crosses $G[v_{0},v_{i},v_{j}]$. As argued
in Observation 3.3, edge $v_{k}v_{\ell}$ must cross $v_{i}v_{j}$, and either
$v_{0}v_{i}$ or $v_{0}v_{j}$ but not both. However, this implies that the
triangle $G[v_{0},v_{k},v_{\ell}]$ does not contain both $v_{i}$ and $v_{j}$,
which is a contradiction. See Figure 2(d). ∎

Let us remark that there can be pairs of vertices $\\{v_{i},v_{j}\\}$ and
$\\{v_{i},v_{\ell}\\}$ in $\Gamma_{4}$ with two directed edges between them in
$\Gamma_{4}$. However, this would only happen if $v_{i},v_{j}\in I_{k,\ell}$
or $v_{k},v_{\ell}\in I_{i,j}$ by the observation above. See Figure 4(b).
Moreover, since $|I_{i,j}|,|I_{k,\ell}|\leq n^{3/4}$, the number of such pairs
is at most $|V(\Gamma_{4})|n^{3/4}$. Since
$|V(\Gamma_{4})|=|M_{4}|\geq(c_{4}/16)n^{3/4}$, by setting $c_{4}$
sufficiently large, the total number of directed edges in $\Gamma_{4}$ is at
most

(a) $v_{k}$ inside $G[v_{0},v_{x},v_{y}]$ and $G[v_{0},v_{i},v_{j}]$.

(b) $v_{k},v_{\ell}\in I_{i,j}$

(c) Matching $\\{v_{i},v_{j}\\}$ not in triangle
$G[v_{0},v_{x^{\prime}},v_{y^{\prime}}].$

Figure 4: Directed edges between $\\{v_{i},v_{j}\\}$ and
$\\{v_{k},v_{\ell}\\}$ in $\Gamma_{4}$.

$\binom{|V(\Gamma_{4})|}{2}+|V(\Gamma_{4})|n^{3/4}\leq\frac{3}{2}\binom{|V(\Gamma_{4})|}{2}.$

Hence, the sum of the in-degree of each vertex in $\Gamma_{4}$ is at most
$\frac{3}{2}\binom{|V(\Gamma_{4})|}{2}.$ By averaging, there is a vertex in
$\Gamma_{4}$ whose in-degree is at most $(3/4)|V(\Gamma_{4})|$. Let us fix
such a matching $\\{v_{x^{\prime}},v_{y^{\prime}}\\}\in V(\Gamma_{4})=M_{4}$.
Hence, there are at least

$\frac{|V(\Gamma_{4})|}{4}=\frac{|M_{4}|}{4}\geq\frac{c_{4}}{64}n^{3/4}$

matchings in $M_{4}$, and thus, in $M_{2}$, that lies in the triangle
$G[v_{0},v_{x},v_{y}]$, but not in $G[v_{0},v_{x^{\prime}},v_{y^{\prime}}].$
See Figure 4(c). On the other hand, there are not too many matchings in
$M_{2}$ that lies in triangle $G[v_{0},v_{x^{\prime}},v_{y^{\prime}}]$, but
not in triangle $G[v_{0},v_{x},v_{y}]$. By the arguments above and Figure
4(a), each such matching must have an endpoint in $I_{x,y}\cup
I_{x^{\prime},y^{\prime}}$. Since $|I_{x,y}|,|I_{x^{\prime},y^{\prime}}|\leq
n^{3/4}$, there are at most $2n^{3/4}$ such matchings in $M_{2}$.

Therefore, for $c_{4}$ sufficiently large, we have

$\displaystyle\phi_{M_{2}}(v_{x^{\prime}},v_{y^{\prime}})$
$\displaystyle\leq\phi_{M_{2}}(v_{x},v_{y})-|M_{4}|/4+2n^{3/4}$
$\displaystyle\leq\phi_{M_{2}}(v_{x},v_{y})-(c_{4}/64)n^{3/4}+2n^{3/4}$
$\displaystyle<\phi_{M_{2}}(v_{x},v_{y}).$

This contradicts the minimality of $\phi_{M_{2}}(v_{x},v_{y})$. Hence

$|E_{4}|\leq(c_{4}/2)n^{3/4}.$ (5)

Combining (1), (2), (3), (4), (5), we conclude that the number of edges in $G$
crossing the topological edge $v_{x}v_{y}$ is at most

$|E_{0}|+|E_{1}|+|E_{2}|+|E_{3}|+|E_{4}|\leq
n+2n^{7/4}+n^{7/4}+c_{3}n^{7/4}+(c_{4}/2)n^{7/4}\leq c_{4}n^{7/4},$

for sufficiently large $c_{4}$. This proves our claim, and completes the proof
of Theorem 1.1.∎

##  4 Concluding remarks

Theorem 1.1 answers one of the questions raised by the author and Zeng in
[18]. It would be interesting if one could improve this bound further.

######  Conjecture 4.1.

For $n\geq 2$, we have $h(n)=\Theta(n^{3/2})$.

It is not even known whether or not every complete $n$-vertex simple
topological graph contains $\Omega(n)$ pairwise disjoint edges. The best known
bound is due to Aicholzer et al. [2], who showed that one can always find
$\Omega(n^{1/2})$ pairwise disjoint edges in a complete $n$-vertex simple
topological graph. See also [17, 7, 14] for slightly weaker polynomial bounds.
A very strong conjecture due to Rafla [13] states that one can always find a
noncrossing Hamiltonian cycle, which has been verified for $n\leq 9$ (see
[1]).

Unfortunately, the proofs in [17, 7, 14, 2] breakdown when trying to find a
noncrossing path rather than disjoint edges. Recently, Aichholzer et al. [2],
and independently, the author and Zeng [18] showed that one can always find a
noncrossing path of length $\Omega(\frac{\log n}{\log\log n})$ in a complete
$n$-vertex simple topological graph. The following was conjectured by the
author and Zeng.

######  Conjecture 4.2 ([18]).

There is an absolute constant $\varepsilon>0$, such that every complete
$n$-vertex simple topological graph contains a noncrossing path on
$n^{\varepsilon}$ vertices.

## References

  * [1] B. Ábrego, O. Aichholzer, S. Fernández-Merchant, T. Hackl, J. Pammer, A. Pilz, P. Ramos, G. Salazar, and B. Vogtenhuber, All good drawings of small complete graphs, _in Proc. 31st European Workshop on Computational Geometry EuroCG ’15_ , pages 57–60, Ljubljana, Slovenia, 2015.
  * [2] O. Aichholzer, A. García, J. Tejel, B. Vogtenhuber, and A. Weinberger, Twisted ways to find plane structures in simple drawings of complete graphs, In _Proc. 38th Symp. Comput. Geometry_ , LIPIcs, Dagstuhl, Germany, 2022, pages 5:1–5:18.
  * [3] P. Brass, W. Moser, J. Pach, _Research Problems in Discrete Geometry_. Berlin, Germany: Springer-Verlag, 2005.
  * [4] B. Chazelle, E. Welzl, Quasi-optimal range searching in spaces of finite VC-dimension, _Discrete Comput. Geom._ 4 (1989), 467–489.
  * [5] R. P. Dilworth, A decomposition theorem for partially ordered sets, _Ann. of Math._ 51 (1950), 161–166.
  * [6] J. Fox, J. Pach, A. Suk, Bounded VC-dimension implies the Schur-Erdos conjecture, _Combinatorica_ 41 (2021), 803–813.
  * [7] R. Fulek and A. Ruiz-Vargas, Topological graphs: empty triangles and disjoint matchings, _in Proceedings of the 29th Annual Symposium on Computational Geometry (SoCG’13)_ , pages 259–266, 2013.
  * [8] H. Harborth, C. Thürmann, Minimum number of edges with at most $s$ crossings in drawings of the complete graph, _Congr. Numer._ 102 (1994), 83–90.
  * [9] D. Haussler, Sphere packing numbers for subsets of the Boolean $n$-cube with bounded Vapnik-Chervonenkis dimension, _J. Combin. Theory Ser. A_ 69 (1995), 217–232.
  * [10] J. Kynčl, P. Valtr, On edges crossing few other edges in simple topological complete graphs, _Discrete Math._ 309 (2009), 1917–1923.
  * [11] J. Matousek, _Geometric Discrepancy: An Illustrated Guide_. Algorithms and combinatorics. 18. Berlin: Springer, 1999.
  * [12] J. Pach and G. Tóth, Disjoint edges in topological graphs, in: _Combinatorial Geometry and Graph Theory (J. Akiyama et al., eds.)_ , Lecture Notes in Computer Science 3330, Springer-Verlag, Berlin, 2005, 133–140.
  * [13] Nabil H. Rafla. The good drawings $D_{n}$ of the complete graph $K_{n}$. PhD thesis, McGill University, Montreal, 1988.
  * [14] A. Ruiz-Vargas, Many disjoint edges in topological graphs, _Comput. Geom._ 62 (2017), 1–13.
  * [15] N. Sauer, On the density of families of sets, _J. of Combin. Theory Ser. A_ 12 (1972), 145–147.
  * [16] S. Shelah, A combinatorial problem, stability and order for models and theories in infinitary languages, _Pacific J. Math._ 41 (1972), 247–261.
  * [17] A. Suk, Disjoint edges in complete topological graphs, _Disc. Comput. Geom._ 49 (2013), 280–286.
  * [18] A. Suk and J. Zeng, Unavoidable patterns in complete simple topological graphs, _Graph Drawing and Network Visualization_ , GD 2022.
  * [19] V. Vapnik and A. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities, _Theory Probab. Appl._ 16 (1971), 264–280.


#  Calculating power integral bases in some quartic fields
corresponding to monogenic families of polynomials

István Gaál
University of Debrecen, Mathematical Institute
H–4002 Debrecen Pf.400., Hungary,
e–mail<EMAIL_ADDRESS>
###### Abstract

J. Harrington and L. Jones [7] characterized monogenity of four new parametric
families of quartic polynomials with various Galois groups. In this note we
intend to describe all generators of power integral bases in the number fields
generated by a root of the monogenic polynomials.

Mathematics Subject Classification: Primary 11Y50, 11R04; Secondary 11D25
Key words and phrases: monogenity; power integral basis; quartic fields; Thue
equations

##  1 Introduction

A number field $K$ of degree $n$ with ring of integers ${\mathbb{Z}}_{K}$ is
called monogenic (cf. [4]) if there exists $\xi\in{\mathbb{Z}}_{K}$ such that
$(1,\xi,\ldots,\xi^{n-1})$ is an integral basis, called power integral basis.
We call $\xi$ the generator of this power integral basis.
$\alpha,\beta\in{\mathbb{Z}}_{K}$ are called equivalent, if
$\alpha+\beta\in{\mathbb{Z}}$ or $\alpha-\beta\in{\mathbb{Z}}_{K}$. Obviously,
$\alpha$ generates a power integral basis in $K$ if and only if any $\beta$,
equivalent to $\alpha$ does. As it is known, any algebraic number field admits
up to equivalence only finitely many generators of power integral bases.

An irreducible polynomial $f(x)\in{\mathbb{Z}}[x]$ is called monogenic, if a
root $\xi$ of $f(x)$ generates a power integral basis in
$K={\mathbb{Q}}(\xi)$. If $f(x)$ is monogenic, then $K$ is monogenic, but the
converse is not true.

For $\alpha\in{\mathbb{Z}}_{K}$ we call the module index
$I(\alpha)=({\mathbb{Z}}_{K}:{\mathbb{Z}}[\alpha])$ the index of $\alpha$.
$\alpha$ generates a power integral basis in $K$ if and only if $I(\alpha)=1$.

In a recent paper J. Harrington and L. Jones [7] gave new infinite parametric
families quartic fields with Galois groups $V_{4}$ (the Klein four group),
$D_{4},A_{4},S_{4}$. They characterized the parameter values for which these
polynomials are monogenic. Our purpose is to describe all generators of power
integral bases in the number fields generated by the roots of these monogenic
polynomials. In some cases we succeeded to give a complete description, in
some other cases we made calculations for parameter values in the interval
$(-1000,1000)$. In the following sections we shall refer to the polynomials of
[7] as $X=2,3,4,5$ as they are denoted in [7].

##  2 Index form equations in quartic fields

We briefly present the results of Gaál, Pethő and Pohst [5], which allows to
reduce index form equations in quartic fields to cubic and quartic Thue
equations. As there are already efficient tools to solve Thue equations, which
are even implemented in algebraic number theory packages like Magma [2], this
is an important tool.

Let $K={\mathbb{Q}}(\xi)$ be a quartic number field and
$f(x)=x^{4}+a_{1}x^{3}+a_{2}x^{2}+a_{3}x+a_{4}\in{\mathbb{Z}}[x]$ the minimal
polynomial of $\xi$. We represent any $\alpha\in{\mathbb{Z}}_{K}$ in the form

$\alpha\;=\;\frac{a_{\alpha}+x\xi+y\xi^{2}+z\xi^{3}}{d}$ (1)

with $a_{\alpha},x,y,z\in{\mathbb{Z}}$, and with a common denominator
$d\in{\mathbb{Z}}$. Consider the solutions of the equation

$I(\alpha)=m\;\;\;\;\;(\alpha\in{\mathbb{Z}}_{K})$ (2)

for $0<m\in{\mathbb{Z}}$. We have

###### Theorem 1

([5]) Let $i_{m}=d^{6}m/n$ where $n=I(\xi)$. The element $\alpha$ of (1) is a
solution of (2) if and only if there is a solution $(u,v)\in{\mathbb{Z}}^{2}$
of the cubic equation

$\displaystyle F(u,v)$ $\displaystyle=$ $\displaystyle
u^{3}-a_{2}u^{2}v+(a_{1}a_{3}-4a_{4})uv^{2}$ (3)
$\displaystyle+(4a_{2}a_{4}-a_{3}^{2}-a_{1}^{2}a_{4})v^{3}=\pm i_{m}$

such that $(x,y,z)$ satisfies

$\displaystyle Q_{1}(x,y,z)$ $\displaystyle=$ $\displaystyle
x^{2}-xya_{1}+y^{2}a_{2}+xz(a_{1}^{2}-2a_{2})+yz(a_{3}-a_{1}a_{2})$
$\displaystyle+z^{2}(-a_{1}a_{3}+a_{2}^{2}+a_{4})=u\;\;,$ $\displaystyle
Q_{2}(x,y,z)$ $\displaystyle=$ $\displaystyle y^{2}-xz-
a_{1}yz+z^{2}a_{2}=v\;\;\;.$ (4)

For a solution $(u,v)$ of (3) we set

$Q_{0}(x,y,z)=uQ_{2}(x,y,z)-vQ_{1}(x,y,z).$

If $\alpha$ in (1) is a solution of (2), then

$Q_{0}(x,y,z)=0.$ (5)

If $(x_{0},y_{0},z_{0})\in{\mathbb{Z}}^{3}$ is a non-trivial solution of (5),
with, say, $z_{0}\neq 0$ (such a solution can be easily found, see L. J.
Mordell [8]), then we can parametrize the solutions $x,y,z$ in the form

$\displaystyle x$ $\displaystyle=$ $\displaystyle rx_{0}+p$ $\displaystyle y$
$\displaystyle=$ $\displaystyle ry_{0}+q$ (6) $\displaystyle z$
$\displaystyle=$ $\displaystyle rz_{0}$

with rational parameters $r,p,q$. Substituting these $x,y,z$ into (5) we
obtain an equation of the form

$r(c_{1}p+c_{2}q)=c_{3}p^{2}+c_{4}pq+c_{5}q^{2},$

with integer coefficients $c_{1},...,c_{5}$. Multiply the equations in (6) by
$c_{1}p+c_{2}q$ and replace $r(c_{1}p+c_{2}q)$ by
$c_{3}p^{2}+c_{4}pq+c_{5}q^{2}$. Further multiply the equations in (6) by the
square of the common denominator of $p,q$ to obtain all integer relations (cf.
[6]). We divide those by $\gcd(p,q)^{2}$ and get

$\displaystyle kx$ $\displaystyle=$ $\displaystyle
c_{11}p^{2}+c_{12}pq+c_{13}q^{2}$ $\displaystyle ky$ $\displaystyle=$
$\displaystyle c_{21}p^{2}+c_{22}pq+c_{23}q^{2}$ (7) $\displaystyle kz$
$\displaystyle=$ $\displaystyle c_{31}p^{2}+c_{32}pq+c_{33}q^{2}$

with integer $c_{ij}$ and integer parameters $p,q$. Here $k$ is an integer
parameter with the property that $k$ divides the $\det(C)/D^{2}$, where $C$ is
the 3x3 matrix with entries $c_{ij}$ and $D$ is the gcd of its entries (cf.
[6]). Finally, substituting the $x,y,z$ in (7) into (4) we obtain

$\displaystyle F_{1}(p,q)$ $\displaystyle=$ $\displaystyle k^{2}u$
$\displaystyle F_{2}(p,q)$ $\displaystyle=$ $\displaystyle k^{2}v$ (8)

###### Theorem 2

([6]) At least one of the equations in (8) is a quartic Thue equation over the
original field $K$.

Equation (3) is either trivial to solve (when $F$ is reducible), or it is a
cubic Thue equation. Using the above parametrization of the variables $x,y,z$
we arrive to the equations (2), at least one of which is a quartic Thue
equation over the original number field $K$, see [6].

##  3 X=2: $f_{t}(x)=x^{4}+4tx^{2}+1$,
Galois group $V_{4}$

The number field generated by a root $\xi$ of $f_{t}(x)=x^{4}+4tx^{2}+1$ is
totally complex for $t\geq 0$ and totally real for $t<0$, By Theorem 1.1 of J.
Harrington and L. Jones [7], $f_{t}(x)$ is monogenic if and only if $4t^{2}-1$
is square-free. In this case $(1,\xi,\xi^{2},\xi^{3})$ is an integral basis in
$K={\mathbb{Q}}(\xi)$. Therefore $n=I(\xi)=1$, in (1) $d=1$, and we are
looking for elements if index $m=1$. Equation (3) gives

$F(u,v)=(u-2v)(u+2v)(u-4tv)=\pm 1.$

The system of equations $u-2v=\pm 1,u+2v=\pm 1,u-4tv=\pm 1$ implies $u=\pm
1,v=0$.

We continue by constructing

$Q_{1}(x,y,z)=x^{2}+4y^{2}t-8xzt+z^{2}(16t^{2}+1),$ (9)
$Q_{2}(x,y,z)=y^{2}-xz+4z^{2}t.$ (10)

By $u=\pm 1,v=0$ we obtain

$Q_{0}(x,y,z)=Q_{2}(x,y,z)=y^{2}-xz+4z^{2}t=0,$ (11)

having the nontrivial solution $x_{0}=1,y_{0}=0,z_{0}=0$. Substituting

$x=rx_{0}=r,\;\;y=ry_{0}+p=p,\;\;z=rz_{0}+q=q$ (12)

into (11) we obtain $p^{2}-rq+4q^{2}t=0$, whence $rq=p^{2}+4tq^{2}$.
Multiplying equations (12) by $q$ and replacing $rq$ by $p^{2}+4tq^{2}$ we
obtain

$\begin{array}[]{cccc}kx=&p^{2}&&+4tq^{2}\\\ ky=&&+pq&\\\
kz=&&&q^{2}\end{array}$ (13)

where $k=\pm 1$ (see the remarks before Theorem 2). Substituting $x,y,z$ of
(13) into (8) we obtain

$F_{1}(p,q)=p^{4}+4p^{2}q^{2}t+q^{4}=\pm 1$ (14)

and the second equation vanishes. If $(p,q)\in{\mathbb{Z}}^{2}$ is a solution
of (14), then so also is $(-p,-q)$, hence we only list one of them.

The trivial solutions of (14) are $(p,q)=(1,0),(0,1)$. If $t\geq 0$, then
obviously there are no more solutions. If $t<0$, then we found that for
$t=-a^{2}$ we also have $(1,\pm 2a),(2a,\pm 1)$. For $-1000\leq t<0$ this was
proved to be all solutions by solving (14) by Magma. This calculation took
5932 sec. Substituting the possible pairs $(p,q)$ into (13) we obtain all
generators of power integral bases.

###### Theorem 3

Assume $4t^{2}-1$ is square-free. Denote by $K$ the number field generated by
a root $\xi$ of $f_{t}(x)=x^{4}+4tx^{2}+1$. For $-1000\leq t$ all generators
of power integral bases are $\xi$ and $4t\xi+\xi^{3}$ with the exception of
parameters of type $t=-a^{2}$ when we additionally have $\pm
2a\xi^{2}+\xi^{3}$ and $(1-16a^{4})\xi\pm 2a\xi^{2}+4a^{2}\xi^{3}$.

##  4 X=3: $f_{t}(x)=x^{4}+24tx^{3}+(12t+4)x^{2}+4x+1$,
Galois group $D_{4}$

The number field $K$ generated by a root $\xi$ of
$f_{t}(x)=x^{4}+24tx^{3}+(12t+4)x^{2}+4x+1$ is totally real for $t<0$, and has
two real roots for $t\geq 0$. By Theorem 1.1 of J. Harrington and L. Jones
$f_{t}(x)$ is monogenic if and only if $36t^{2}-1$ is square-free. In these
cases (similarly to the case X=2) we have

$F(u,v)=(u-12vt)(u^{2}-4uv+v^{2}(48t-4)=\pm 1$

hence $u-12tv=\pm 1,u=e+12tv$ with $e=\pm 1$. We substitute $u$ into the
second factor of $F(u,v)$ and then obtain two possible cases:
A. $(144t^{2}-4)v^{2}\pm(24t-4)v+2=0$. This is a second degree equation in
$v$. For $t\neq 0$ the discriminant is negative, for t=0 it is not a square.
B: $(144t^{2}-4)v^{2}\pm(24t-4)v=0$. In this case either $v=0,u=\pm 1$ or
$v=\pm\frac{24t-4}{144t^{2}-4}$. For $t\neq 0$ this gives no solution for $v$.
For $t=0$ we obtain $v=\pm 1$, but no solution for $u$.

For the solution $(u,v)=(\pm 1,0)$ similarly as for $X=2$ we obtain

$Q_{1}(x,y,z)=x^{2}-24xyt+y^{2}(12t+4)+xz(576t^{2}-24t-8)+yz(-288t^{2}-96t+4)$
$+z^{2}(144t^{2}+17)$ $Q_{2}(x,y,z)=y^{2}-xz-24yzt+z^{2}(12t+4)$

and

$Q_{0}(x,y,z)=Q_{2}(x,y,z)=y^{2}-xz-24yzt+z^{2}(12t+4).$

This has the nontrivial solution $x_{0}=1,y_{0}=0,z_{0}=0$. Substituting
$x=rx_{0}=r,\;\;y=ry_{0}+p=p,\;\;z=rz_{0}+q=q$ into $Q_{0}(x,y,z)=0$ we obtain
$rq=p^{2}-24tpq+q^{2}(12t+4)$, whence $rq=p^{2}-24tpq+q^{2}(12t+4)$.
Multiplying the equations $x=r,y=p,z=q$ by $q$ and performing the above
substituting of $rq$ we obtain

$\begin{array}[]{cccc}kx=&p^{2}&-24tpq&+q^{2}(12t+4)\\\ ky=&&+pq&\\\
kz=&&&q^{2}\end{array}$ (15)

As in X=2 we have $k=\pm 1$. Substituting the above representations of $x,y,z$
into $Q_{1}(x,y,z)=u$ and $Q_{2}(x,y,z)=v$ we have

$F_{1}(p,q)=p^{4}-72tp^{3}q+p^{2}q^{2}(1728t^{2}+12t+4)+pq^{3}(-13824t^{3}-576t^{2}-192tpq^{3}+4)$
$+q^{4}(6912t^{3}+2304t^{2}-96q^{4}+1)$

and $F_{2}(p,q)$ vanishes. By $p=a+24bt,q=b$ we get

$F_{1}(a,b)=a^{4}+24ta^{3}b+(12t+4)a^{2}b^{2}+4ab^{3}+b^{4}=\pm 1.$

We solved this quartic Thue equation by Magma for $-1000\leq t\leq 1000$. This
calculation took 20476 seconds. Up to sign we got the solutions
$(a,b)=(1,0),0,1),(1,-2)$. One can check that these are solutions for any $t$.
Moreover if $t<0$ and $1-2t$ is a square, then we also obtained
$(a,b)=(1,-1+\sqrt{1-2t}),(1,-1-\sqrt{1-2t})$. Equivalently, if
$t=-(n^{2}+2n)/12$ is an integer, then $(a,b)=(1,n),(1,-n-2)$ are solutions.
One can also check that for $t$ of this type, these are solutions in general,
not only for $-1000\leq t$.

By $p=a+24bt,q=b$ and (15) we obtain

###### Theorem 4

Assume $36t^{2}-1$ is square-free. Denote by $K$ the number field generated by
a root $\xi$ of $f_{t}(x)=x^{4}+24tx^{3}+(12t+4)x^{2}+4x+1$. For $-1000\leq
t\leq 1000$ all generators of power integral bases are
$\xi,\;\;(12t+4)\xi+24t\xi^{2}+\xi^{3},\;\;17\xi+(-2+96t)\xi^{2}+4\xi^{3}$.
Moreover, if $1-2t$ is a square, or equivalently if $t=-(n^{2}+2n)/12$ is an
integer, then we also have
$(-n^{4}-4n^{3}+1)\xi+(-2n^{4}-4n^{3}+n)\xi^{2}+n^{2}\xi^{3}$ and
$(-n^{4}-4n^{3}+16n+17)\xi+(-2n^{4}-12n^{3}-24n^{2}-17n-2)\xi^{2}+(n^{2}+4n+4)\xi^{3}$.

##  5 X=4: $f_{t}(x)=x^{4}+2x^{3}+2x^{2}+4tx+36t^{2}-16t+2$,
Galois group $A_{4}$

The number field $K$ generated by a root $\xi$ of
$f_{t}(x)=x^{4}+2x^{3}+2x^{2}+4tx+36t^{2}-16t+2$ is totally complex. By
Theorem 1.1 of J. Harrington and L. Jones $f_{t}(x)$ is monogenic if and only
if $(4t-1)(108t^{2}-54t+7)$ is square-free. In these cases, similarly to the
case X=2 we obtain

$F(u,v)=u^{3}-2u^{2}v+(72t-144t^{2}-8)uv^{2}+(128t^{2}-64t+8)v^{3}=\pm 1.$

The polynomial $F(u,1)$ has three real roots. Solving the above equation by
Magma for $-1000\leq t\leq 1000$. We obtained $(u,v)=(1,0)$ for any $t$ and
additionally $(u,v)=(1,1),(5,-2)$ for $t=0$. This calculation took 1600
seconds. We obtain

$Q_{1}(x,y,z)=x^{2}-2xy+2y^{2}+yz(4t-4)+z^{2}(-24t+6+36t^{2})$
$Q_{2}(x,y,z)=y^{2}-xz-2yz+2z^{2}.$

For the solution $(u,v)=(1,0)$ we set

$Q_{0}(x,y,z)=Q_{2}(x,y,z)=y^{2}-xz-2yz+2z^{2}.$

The equation $Q_{0}(x,y,z)=0$ has a nontrivial solution
$x_{0}=1,y_{0}=0,z_{0}=0$. Substituting
$x=rx_{0}=r,\;\;y=ry_{0}+p=p,\;\;z=rz_{0}+q=q$ into $Q_{0}(x,y,z)=0$ we obtain
$rq=p^{2}-2pq+2q^{2}$. Multiplying by $q$ the equations $x=r,y=p,z=q$ and
performing the above replacement of $rq$ we get

$\begin{array}[]{cccc}kx=&p^{2}&-2pq&+2q^{2}\\\ ky=&&+pq&\\\
kz=&&&q^{2}\end{array}$

Similarly as before we have $k=\pm 1$. Substituting the above representations
of $x,y,z$ into $Q_{1}(x,y,z)=\pm 1$ and $Q_{2}(x,y,z)=0$ we obtain

$F_{1}(p,q)=p^{4}-6p^{3}q+14p^{2}q^{2}+pq^{3}(4t-16)+q^{4}(36t^{2}-24t+10)=\pm
1$

and $F_{2}(p,q)$ vanishes. Substituting $p=a+2b,q=b$ into the first equation
we get

$F_{1}(a,b)=a^{4}+2a^{3}b+2a^{2}b^{2}+4tab^{3}+b^{4}(36t^{2}-16t+2)=\pm 1$

We solved this equation by Magma for $-1000\leq t\leq 1000$, it took 10309
seconds. We found the solution $(a,b)=(1,0)$ which gives $(p,q)=(1,0)$,
$(x,y,z)=(1,0,0)$.

Performing similar calculations in the case $t=0$, for $(u,v)=1,1)$ we get
$(x,y,z)=(1,1,0)$ and $(u,v)=(5,-2)$ does not give further solutions.

###### Theorem 5

Assume $(4t-1)(108t^{2}-54t+7)$ is square-free. Denote by $K$ the number field
generated by a root $\xi$ of $f_{t}(x)=x^{4}+2x^{3}+2x^{2}+4tx+36t^{2}-16t+2$.
For $-1000\leq t\leq 1000$ all generators of power integral bases are $\xi$,
for $t=0$ we additionally have $\xi+\xi^{2}$.

##  6 X=5: $f_{t}(x)=x^{4}-2x^{3}-2x^{2}+6x+4t-2$,
Galois group $S_{4}$

Let $K$ be the number field generated by a root $\xi$ of
$f_{t}(x)=x^{4}-2x^{3}-2x^{2}+6x+4t-2$. This polynomial has two real roots for
$t\leq 1$ and is totally complex for $t\geq 2$. According to Theorem 1.1 of J.
Harrington and L. Jones $f_{t}(x)$ is monogenic if and only if $4t+1$, $4t-7$
and $64t+13$ are square-free. In these cases, similarly to the case X=2 we
obtain

$F(u,v)=u^{3}+2u^{2}v+(-4-16t)uv^{2}+(-48t-12)v^{3}=\pm 1.$

This polynomial $F(u,1)$ has one real root for $t\leq 1$ and is totally real
for $t\geq 2$. We solve the above equation for $-1000\leq t\leq 1000$ by
Magma. It took 39125 seconds. We found the solution $(u,v)=(1,0)$ for any $t$
and for $t=95$ additionally $(u,v)=(77,-2)$.
Corresponding to $(u,v)=(1,0)$ we obtain

$Q_{1}(x,y,z)=x^{2}+2xy-2y^{2}+8xz+2yz+z^{2}(14+4t)$
$Q_{2}(x,y,z)=y^{2}-xz+2yz-2z^{2}.$

Similarly as before we construct

$Q_{0}(x,y,z)=Q_{2}(x,y,z)=y^{2}-xz+2yz-2z^{2}.$

A nontrivial solution of $Q_{0}(x,y,z)=0$ is $x_{0}=1,y_{0}=0,z_{0}=0$. We set
$x=rx_{0}=r,\;\;y=ry_{0}+p=p,\;\;z=rz_{0}+q=q$, substitute it into
$Q_{0}(x,y,z)=0$ and obtain $rq=p^{2}+2pq-2q^{2}$. Multiplying the equations
$x=r,y=p,z=q$ by $q$ and performing the above substitution of $rq$ we obtain

$\begin{array}[]{cccc}kx=&p^{2}&-2pq&+2q^{2}\\\ ky=&&+pq&\\\
kz=&&&q^{2}\end{array}$

Similarly as before we have $k=\pm 1$. Substituting these representations of
$x,y,z$ into $Q_{1}(x,y,z)=\pm 1$ and $Q_{2}(x,y,z)=0$ we obtain

$F_{1}(p,q)=p^{4}+6p^{3}q+10p^{2}q^{2}+6pq^{3}+2q^{4}+4q^{4}t=\pm 1$

and $F_{2}(p.q)$ vanishes. Setting $p=a-2b,q=b$ into the first equation we get

$F_{1}(a,b)=a^{4}-2a^{3}b-2a^{2}b^{2}+6ab^{3}-2b^{4}+4b^{4}t=\pm 1.$

We solved this equation by Magma for $-1000\leq t\leq 1000$, it took 1671
seconds. We obtained $(a,b)=(1,0)$ for any $t$ and the following solutions for
special values of $t$:
$t=-736,(a,b)=(7,-1)$
$t=-620,(a,b)=(23,3)$
$t=-414,(a,b)=(7,1)$
$t=-198,(a,b)=(5,-1)$
$t=-88,(a,b)=(5,1)$
$t=-24,(a,b)=(3,-1)$
$t=-6,(a,b)=(3,1)$
$t=0,(a,b)=(1,1)$
$t=2,(a,b)=(1,-1)$
We did not find any rule producing these parameter values or solutions.

In case $t=95$ we additionally have the solution $(u,v)=(77,-2)$ of
$F(u,v)=\pm 1$. Performing the similar calculations we do not obtain any
solutions for $(a,b)$. Solving 8 quartic Thue equations took a negligible
amount of time by Magma.

###### Theorem 6

Assume $4t+1$, $4t-7$ and $64t+13$ are square-free. Denote by $K$ the number
field generated by a root $\xi$ of $f_{t}(x)=x^{4}-2x^{3}-2x^{2}+6x+4t-2$. For
$-1000\leq t\leq 1000$ $\xi$ is the only generator of power integral bases
except the following parameters, when we have some additional generators of
power integral bases:
$t=-736,\;\;101\xi-9\xi^{2}+\xi^{3}$
$t=-620,\;\;205\xi+51\xi^{2}+9\xi^{3}$
$t=-414,\;\;17\xi+5\xi^{2}+\xi^{3}$
$t=-198,\;\;65\xi-7\xi^{2}+\xi^{3}$
$t=-88,\;\;5\xi+3\xi^{2}+\xi^{3}$
$t=-24,\;\;37\xi-5\xi^{2}+\xi^{3}$
$t=-6,\;\;\xi+\xi^{2}+\xi^{3}$
$t=0,\;\;5\xi-\xi^{2}+\xi^{3}$
$t=2,\;\;17\xi-3\xi^{2}+\xi^{3}$

##  7 Computational remarks

All auxiliary calculations were made by Maple [3] taking negligible amount of
time. The resolution of Thue equations were performed by using Magma [2],
requiring all together 79113 seconds, or equivalently about 22 hours.

## References

  * [1]
  * [2] W. Bosma, J. Cannon and C. Playoust, The Magma Algebra System. I. The User Language. J. Symbolic Comput. 24(1997), 235-265.
  * [3] B. W. Char, K. O. Geddes, G. H. Gonnet, M. B. Monagan, S. M. Watt (eds.), MAPLE, Reference Manual, Watcom Publications, Waterloo, Canada, 1988.
  * [4] I. Gaál, Diophantine equations and power integral bases. Theory and algorithms. 2nd edition, Birkhäuser, Boston, 2019.
  * [5] I. Gaál, A. Pethő and M. Pohst, On the resolution of index form equations in quartic number fields, J. Symbolic Comput., 16(1993), 563–584.
  * [6] I. Gaál, A. Pethő and M. Pohst, Simultaneous representation of integers by a pair of ternary quadratic forms – with an application to index form equations in quartic number fields, J. Number Theory, 57(1996), 90–104.
  * [7] J. Harrington and L. Jones, Monogenic quartic polynomials and their Galois groups, arXiv:2404.05487v2.
  * [8] L. J. Mordell, Diophantine Equations, Academic Press, New York–London, 1969.