# Continued Fractions and the $4$-Color Theorem

Richard Evan Schwartz Supported by N.S.F. Grant DMS-2102802

###### Abstract

We study the geometry of some proper $4$-colorings of the vertices of sphere
triangulations with degree sequence $6,...,6,2,2,2$. Such triangulations are
the simplest examples which have non-negative combinatorial curvature. The
examples we construct, which are roughly extremal in some sense, are based on
a novel geometric interpretation of continued fractions. We will also present
a conjectural sharp “isoperimetric inequality” for colorings of this kind of
triangulation.

##  1 Introduction

###  1.1 Background

The Four Color Theorem, first proved (with the assistance of a computer) by
Wolfgang Haken and Kenneth Appel in $1976$, is one of the most famous results
in mathematics. See [W] for a thorough discussion. Here is one formulation. If
you have any triangulation of the $2$-sphere, it is possible to color the
vertices using $4$ colors such that no two adjacent vertices have the same
coloring. This is called a proper vertex $4$-coloring.

Certainly one can properly $4$-color the vertices of a tetrahedron. A proper
vertex $4$-coloring of a triangulation $\cal Z$ (with the same colors)
canonically defines a simplicial map $f$ from the sphere to the tetrahedron:
Just map each vertex of $\cal Z$ to the like-colored vertex of the tetrahedron
and then extend linearly to the faces. The map $f$ in turn defines a
$2$-coloring of the faces of $\cal Z$. One colors a face of $\cal Z$ black if
$f$ is orientation preserving on that face, and otherwise white.

The associated face $2$-coloring has the property that around each vertex the
number of black faces is congruent mod $3$ to the number of white faces. This
derives from the property that $3$ triangles of the tetrahedron meet around
each vertex. We call a face $2$-coloring with this property a good coloring.
Conversely, a good coloring for $\cal Z$ defines a simplicial map to the
tetrahedron and thus a proper $4$-coloring of the vertices of $\cal Z$. So, an
equivalent formulation of the $4$-color theorem is that every triangulation of
the sphere has a good coloring.

So far, the Four Color Theorem only has computer-assisted proofs. Perhaps one
can get insight into the result by looking at examples of good colorings. The
good coloring version has a geometric feel to it, and so perhaps some
geometric insight might help. The purpose of this paper is to look at the
geometry of these good colorings in some special cases.

A triangulation of non-negative combinatorial curvature is one in which the
maximum degree is $6$. All the vertices have degree $6$ except for a list
$v_{1},...,v_{k}$ which have degrees $2\leq d_{1},...,d_{k}<6$. Euler’s
Formula gives the condition on the degrees:

$\sum_{i=1}^{k}(6-d_{i})=12.$ (1)

In particular $k\leq 12$. The quantity

$\frac{\pi}{3}\times(6-d_{i})$

is the combinatorial curvature at $v_{i}$. Equation 1 translates into a
discrete version of the Gauss-Bonnet theorem, which says that the total
combinatorial curvature is $4\pi$.

The triangulations of non-negative combinatorial curvature form an attractive
family to study. In [T], William Thurston organized these triangulations into
moduli spaces. To give some idea of how this works, a triangulation of non-
negative combinatorial curvature defines a flat cone structure on the sphere
with non-negative curvature: we just make all the triangles unit equilateral
triangles. The set of all triangulations with the same list $d_{1},..,d_{k}$
of defects includes in the moduli space of flat cone structures on spheres
with appropriately prescribed singularities. So, even though the
triangulations don’t exactly vary continuously, one can think of them as
special points inside moduli spaces consisting of structures which do vary
continuously. Also, if the triangulations involve many triangles and the
defects are well spread out, one can imagine that the defects almost vary
continuously.

Given the nice structure of the totality of such triangulations, it seems like
an interesting idea to study the space of good colorings as a kind of
partially defined bundle over these moduli spaces. Perhaps the structure of
such colorings is related somehow to the placement of the defects. As the
defects vary around, perhaps the good colorings vary in a nice way to some
extent. I imagine that the total picture, seen all at once, would be
spectacularly beautiful. All this is very speculative. In spite of making a
lot of computer experiments over the years – every time I teach the graph
theory class at Brown I play with this project – I don’t have much to report.
In this very modest paper I will consider the simplest cases. The cases I have
in mind are where $k=3$ and $d_{1}=d_{2}=d_{3}=2$.

###  1.2 The Continued Fraction Colorings

The $6,...,6,2,2,2$ trianglulations are indexed by the nonzero Eisenstein
integers. An Eisenstein integer is a number of the form

$a+b\alpha,\hskip 30.0pta,b\in\mbox{\boldmath{$Z$}},\hskip
15.0pt\alpha=\frac{1+i\sqrt{3}}{2}.$

(It is more common to use $\omega=\alpha^{2}$ in place of $\alpha$, but
$\alpha$ is more convenient for us.) To see the connection, let $\cal E$
denote the ring of Eisenstein integers. The points of $\cal E$ are naturally
the vertices of an equilateral triangulation $\cal T$ of $C$. Given some
nonzero $\beta\in\cal E$, we let $\beta\cal T$ be the bigger equilateral
triangulation obtained by multiplying the whole picture by $\beta$. We let
$G_{\beta}$ denote the group of symmetries generated by order $3$ rotations in
the vertices of $\beta\cal T$. The quotient

${\cal T\/}(\beta)={\cal T\/}/G_{\beta}$

is the desired triangulation.

Since all the vertices of ${\cal T\/}(\beta)$ have even degree, ${\cal
T\/}(\beta)$ always has a good coloring. One just colors the triangles
alternately black and white in a checkerboard pattern. Indeed, this face
coloring corresponds to a proper $3$-coloring of the vertices.

Figure 1 shows a different good coloring for $\beta=2+3\alpha$. We call this
coloring ${\cal C\/}(2+3\alpha)$. To get the triangulation of the sphere, cut
out the specially outlined central rhombus, fold it up like a taco, and glue
the edges together in pairs. Figure 1 is really showing part of the orbifold
universal cover of the coloring. Figures 7 and 8 below show more elaborate
examples.

Figure 1: The good coloring ${\cal C\/}(2+3\alpha)$ of ${\cal
T\/}(2+3\alpha)$.

The coloring in Figure 1 is (at least experimentally) extremal in a certain
sense. Define the fold count of a good coloring to be the number of edges
which form black-white interfaces. For the alternating coloring, the fold
count is $3/2$ times the number of faces. For ${\cal T\/}(2+3\alpha)$ this
comes to $57$. In contrast, ${\cal C\/}(2+3\alpha)$ has fold count $23$. It
seems that ${\cal C\/}(2+3\alpha)$ minimizes the fold count amongst all good
colorings of ${\cal T\/}(2+3\alpha)$.

The number of good colorings of ${\cal T\/}(\beta)$ grows exponentially with
$|\beta|$, for an easy reason. In any good coloring, if we can find a vertex
of degree $6$ where the colors alternate, we can switch the colors and get
another good coloring. In terms of the original vertex coloring, the neighbors
of such a vertex $v$ are colored using just $2$ colors, and so we have an
option to switch the color of $v$ to the other available color. Starting with
the alternating coloring, we can take a large family of non-adjacent vertices
and make these swaps according to any binary sequence we like. On the other
hand, these examples seem rather similar to the alternating coloring. Their
fold count is linear in the number of the faces.

The colorings with smaller fold counts, and in particular with minimal fold
counts, seem to be much more rigid and interesting. To use an analogy from
statistical mechanics, the colorings with large fold count are sort of like a
fluid or a gas, and the colorings with small fold count are more like solid
crystals. The example in Figure 1 is part of an infinite sequence of examples.
We call these examples ${\cal C\/}(\beta)$, where $\beta$ ranges over the
primitive Eisenstein integers. (An Eisenstein integer $\beta=a+b\alpha$
primitive if it is not an integer multiple of another one. Equivalently, $a$
and $b$ are relatively prime.) We will see that ${\cal C\/}(\beta)$ is a
special good coloring of ${\cal T\/}(\beta)$ which geometrically implements
the continued fraction expansion of $a/b$. We call these colorings continued
fraction colorings.

###  1.3 Properties of the Continued Fraction Colorings

The main result of this paper is that these continued fraction colorings
exist, but I will prove some additional results about them. One interesting
property is that these colorings have the same number of black and white
triangles. Indeed, any good coloring of a triangulation having all even
degrees has the same number of black and white triangles. See §3.1 for the
quick proof which I learned from Kasra Rafi.

Our next result concerns the asymptotics of the fold count for the continued
fraction colorings. Let $\\{a_{n}/b_{n}\\}\in(0,1)$ be a sequence of
rationals. Let

${\cal T\/}_{n}={\cal T\/}(a_{n}+b_{n}\alpha),\hskip 30.0pt{\cal
C\/}_{n}={\cal C\/}(a_{n}+b_{n}\alpha).$

Let $f_{n}$ denote the fold count of ${\cal C\/}_{n}$ and let $F_{n}$ denote
the number of faces in ${\cal T\/}_{n}$.

###### Theorem 1.1

The following is true about the continued fraction colorings.

  1. 1.

If $\\{a_{n}/b_{n}\\}$ converges to an irrational limit then
$\lim_{n\to\infty}f_{n}/F_{n}=0$.

  2. 2.

If $\\{a_{n}/b_{n}\\}$ is the sequence of continued fraction approximants of a
quadratic irrational, then $\lim_{n\to\infty}f_{n}^{2}/F_{n}$ exists and is
finite.

Statement 2 of Theorem 1.1 motivates the following definitions.

Definition: Given a coloring $\cal C$ we define

$\eta({\cal C\/})=\frac{f^{2}}{F},$ (2)

where $f$ is the fold count for $\cal C$ and $F$ is the number of triangles in
the triangulation which $\cal C$ colors. We call $\eta({\cal C\/})$ the
Eisenstein Isoperimetric Ratio of $\cal C$.

Definition: Given a quadratic irrational $\eta\in(0,1)$ let

$\eta(\zeta)=\lim_{n\to\infty}\eta(p_{n}+q_{n}\alpha),$

where $\\{p_{n}/q_{n}\\}$ is the sequence of continued fraction approximants
of $\zeta$. Theorem 1.1 guarantees that this limit exists. We call
$\eta(\zeta)$ the Eisenstein Isoperimetric Ratio of $\zeta$.

In §3.3 we will show, among other calculations, that

$\eta(\phi^{-1})=\phi^{6},\hskip 30.0pt\phi=\frac{\sqrt{5}+1}{2}.$ (3)

Here $\phi$ is the golden ratio. Our proof of Statement 2 of Theorem 1.1 will
show more generally that $\eta(\zeta)\in\mbox{\boldmath{$Q$}}(\zeta)$, the
quadratic field containing $\zeta$. See §3.3 for some examples.

For comparison we prove the following easy result.

###### Theorem 1.2

Let $\cal C$ be any good coloring of any triangulation with degree sequence
$6,...,6,2,2,2$. Then $\eta({\cal C\/})\geq 3$.

Theorem 1.2 indicates that some of the continued fraction colorings roughly
minimize the fold count. Here is a strong conjecture along these lines.

###### Conjecture 1.3

Suppose $\\{{\cal G\/}_{n}\\}$ is any infinite sequence of distinct colorings
of primitive sphere triangulations with degree sequence $6,...,6,2,2,2$. Then
$\liminf_{n\to\infty}\eta({\cal G\/}_{n})\geq\phi^{6}$.

Here primitive means that the triangulation has the form ${\cal T\/}(\beta)$
for a primitive Eisenstein integer $\beta$. Equation 3 says that this
conjecture is sharp. Since $\phi^{6}=17.944...<18$, Theorem 1.2 says that the
conjecture is true up to a factor of $6$.

Sometimes there are good colorings which have lower fold count then the
corresponding continued fraction coloring. See Figure 9 in §3 for an example.
Here is one last conjecture about the general situation.

###### Conjecture 1.4

There is a constant $\Omega$ with the following property. For any
triangulation $\cal T$ with degree sequence $6,....,6,2,2,2$ there is a good
coloring $\cal C$ of $\cal T$ with $\eta({\cal C\/})<\Omega$.

###  1.4 Organization

In §2, after a discussion of the slow Gauss map and its connection to
continued fractions, I will construct the continued fraction colorings. The
building blocks are what I call capped flowers, and these in turn are made in
layers from cyclically arranged patterns of trapezoids which I call trapezoid
necklaces. (Look again at Figure 1.) I will explain how the set of trapezoid
necklaces is naturally the vertex set of the infinite rooted binary tree
(modified to have an extra vertex at the bottom). Taking a path in this tree
defines the capped flower. In §3 I will prove Theorem 1.1, establish Equation
3, and give some evidence for Conjecture 1.3. In §4 I will prove Theorem 1.2.

###  1.5 Acknowledgements

I’d like to thank Ethan Bove, Peter Doyle, Jeremy Kahn, Rick Kenyon, Curtis
McMullen, Kasra Rafi, and Peter Smillie for various conversations (sometimes
going back some years) on topics related to the material here.

##  2 The Main Construction

###  2.1 The Slow Gauss Map

Given $r\in(0,1)$ we define $\gamma(r)$ to be whichever of the two numbers

$\frac{1}{r}-1\hskip 30.0pt{\rm or\/}\hskip 30.0pt\frac{1}{\frac{1}{r}-1}$ (4)

lies in $(0,1]$. When $r>1/2$ the first choice works and when $r<1/2$ the
second choice works. When $r=1/2$ both choices give $\gamma(1/2)=1$. The map
$\gamma:(0,1)\to(0,1]$ is called the slow Gauss map.

Let $\cal S$ denote the set of rationals in $(0,1]$. On ${\cal S\/}-\\{1\\}$
we have:

$\gamma\bigg{(}\frac{a}{a+b}\bigg{)}=\gamma\bigg{(}\frac{b}{a+b}\bigg{)}=\frac{a}{b}.$
(5)

We can think of $\cal S$ as the infinite rooted binary tree (modified to have
an extra bottom vertex). We make this tree by joining each member of ${\cal
S\/}-\\{1\\}$ to its image under $\gamma$. Figure 2 shows the beginning of
this tree.

Figure 2: The beginning of the tree of rationals.

The slow Gauss map is connected to continued fractions. The traditional Gauss
map is

$\gamma^{*}(p/q)=(q/p)-{\rm floor\/}(q/p).$ (6)

For each $p/q$ there is some comparison exponent $k$ such that

$\gamma^{*}(p/q)=\gamma^{k}(p/q).$

In other words, the (suitably) iterated slow Gauss map has the same action as
the traditional Gauss map; it just works more slowly. The continued fraction
expansion of $p/q$ is obtained by recording the sequence of comparison
exponents we see as we iteratively apply $\gamma$ and $\gamma^{*}$ to $p/q$.

###  2.2 Trapezoid Necklaces

An isosceles trapezoid is a quadrilateral with two parallel sides such that
the other two sides are non-parallel but have the same length. We call the
longer parallel side the top, the shorter parallel side the bottom, and the
other two sides the diagonal sides. We allow the degenerate case of an
isosceles triangle. In this case the bottom has length $0$. An Eisenstein
trapezoid is an isosceles trapezoid whose edges lie in the $1$-skeleton of
$\cal T$, the planar equilateral triangulation whose vertices are the
Eisenstein integers. Figure 1 above and Figure 3 below feature some Eisenstein
trapezoids.

Up to symmetries of $\cal T$, an Eisenstein trapezoid $X$ is characterized by
the pair $(a,b)$ where $a$ is the length of a diagonal side of $X$ and $b$ is
the length of the top. We call $X$ primitive if $a,b$ are relatively prime.
When $X$ is primitive, we define the aspect ratio to be $a/b$. The aspect
ratio determines the primitive Eisenstein trapezoid up to symmetries of $\cal
T$. Thus, modulo symmetry, the primitive Eisenstein trapezoids are naturally
in bijection with the set $\cal S$ of rationals considered above. The
Eisenstein trapezoids in Figure 1 are all primitive, and their aspect ratios
are variously $1/1$ and $1/2$ and $2/3$. The Eisenstein trapezoids in Figure 3
have aspect ratio $3/5$.

Figure 3: A trapezoid necklace of aspect ratio $3/5$.

Figure 3 illustrates what we mean by a trapezoid necklace. This is a union of
$6$ primitive Eisenstein trapezoids $X_{1},...,X_{6}$ which has the following
properties:

  * •

The trapezoids have pairwise disjoint interiors.

  * •

$X_{i}\cap X_{i+1}$ is a single point, a common vertex, for all $i$.

  * •

An order $6$ rotation $\rho$ of $\cal T$ has the action $\rho(X_{i})=X_{i+1}$
for all $i$.

In this description the indices are taken mod $6$. We define the center of the
necklace to be the fixed point of $\rho$. When the center is $0$, the map
$\rho$ (or perhaps its inverse) is multiplication by $\alpha$. We define the
aspect ratio of the necklace to be the common aspect ratio of the $6$
individual trapezoids.

Up to symmetry of $\cal T$, there exists a unique Eisenstein necklace of
aspect ratio $a/b\in\cal S$. If we normalize the picture so that $0$ is the
center, then one of the trapezoids $X_{1}$ has vertices

$a+b\alpha,\hskip 30.0pt(a-b)+b\alpha,\hskip 30.0pt(2a-b)+(b-a)\alpha,\hskip
30.0pta+(b-a)\alpha.$

The intersection of $X_{1}$ and $X_{2}=\rho(X_{1})$ is the point
$(a-b)+b\alpha$ because

$\alpha\times\big{(}a+(b-a)\alpha)=(a-b)+b\alpha.$

This little calculation uses the fact that $\alpha^{2}=\alpha-1$.

###  2.3 Empty Trapezoid Flowers

Each trapezoid necklace $X$ defines a smaller trapezoid necklace $Y=\gamma(X)$
having the same center. The defining property is that the top side of each
trapezoid $Y_{i}$ in $Y$ is a side of a trapezoid $X_{j}$ of $X$, and one of
the diagonal sides of $Y_{i}$ is a side of one of the trapezoids of $X$
adjacent to $X_{j}$. This awkward definition is very much like a written
description of how to drink a glass of water. A demonstration says a thousand
words. Figure 4 shows the trapezoid necklaces

$X\to\gamma(X)\to\gamma^{2}(X)\to\gamma^{3}(X)$

alternately colored black and white. Here $X$ is as in Figure 3. The
respective aspect ratios are given by $3/5\to 2/3\to 1/2\to 1/1$. We call the
union of these necklaces the empty $3/5$-flower.

Figure 4: The empty $3/5$-flower.

As is suggested by our notation, the action of $\gamma$ here mirrors the
action of the slow Gauss map $\gamma$ defined above. That is, if $r$ is the
aspect ratio of $X$ then $\gamma(r)$ is the aspect ratio of $\gamma(X)$.

We discussed above how the slow Gauss map is related to continued fractions.
Here we continue the discussion. As we now illustrate, our construction also
precisely implements the continued fraction expansion.

Figure 5: The empty $3/7$-flower.

Figure 5 shows the empty $3/7$-flower, corresponding to the tree path $3/7\to
3/4\to 1/3\to 1/2\to 1/1$. The specially-outlined trapezoids (and their
rotated images) are the maximal trapezoids in the flower. They have
respectively $2$ and $3$ “stripes”. For comparison, $3/7$ has continued
fraction $0:2:3$. That is

$\frac{3}{7}=0+\frac{1}{2+\frac{1}{3}}.$

In general, the empty $p/q$-flower starts with a $p/q$-necklace and then fills
in the full $\gamma$ orbit, alternately coloring the necklaces black and
white. The innermost necklace always has aspect ratio $1/1$. Up to symmetries
of $\cal T$, the empty $p/q$-flower is unique. One can read off the continued
fraction expansion of $p/q$ by counting the stripes of the maximal trapezoids.

###  2.4 Filling and Capping the Flowers

We fill an empty flower by coloring the remaining $6$ triangles black and
white in an alternating pattern. Figure 6 shows this for the $3/5$-flower. Up
to symmetries of $\cal T$ (and swapping the colors) there is a unique
$p/q$-flower. The empty flowers have $6$-fold rotational symmetry but the
(filled) flowers have $3$-fold rotational symmetry. We break a symmetry to
define the filling.

Figure 6: The filled and capped $3/5$-flower

Figure 6 also shows what we mean by capping a flower. We take the convex hull
of the flower and color the complementary triangles the color opposite the
color of the outer necklace. The capped flowers, which are regular hexagons
with Eisenstein integer vertices, are the building blocks of our colorings.
When two translation-equivalent capped flowers meet along a common boundary
edge, the triangular regions merge to become an Eisenstein parallelogram –
i.e., one whose boundary lies in the $1$-skeleton of $\cal T$.

###  2.5 Defining the Colorings

Consider the hexagonal tiling of the plane by translates of the capped
$a/b$-flower. Because the capped flowers have $3$-fold rotational symmetry,
the resulting planar coloring is invariant under the group $G_{\beta}$
generated by order $3$ reflections in the vertices and centers of the
hexagons. The quotient of this planar coloring by $G_{\beta}$ is ${\cal
C\/}(\beta)$. By construction, ${\cal C\/}(\beta)$ is good.

Figure 7: The universal cover of ${\cal C\/}(3+5\alpha)$.

Figure 7 shows the construction for $\beta=3+5\alpha$. The region bounded by
the big central rhombus is a fundamental domain for the action of $G_{\beta}$.
The colorings exhibit a lot of variety. Figure 8 below shows ${\cal
C\/}(a+13\alpha)$ for $a=1,3,5,7,9,11$. It is worth noting that for parameters
like $1/13$ the fold count is linear in the number of triangles.

Figure 8: The orbifold covers of ${\cal C\/}(a+13\alpha)$ for
$a=1,3,5,7,9,11.$.

##  3 Properties of the Colorings

###  3.1 Zero Degree

Let $T$ denote the regular tetrahedron. Call a triangulation of the sphere
even if it has all even degrees. In this section we prove that any good
coloring of an even triangulation $\Sigma$ has the same total number of black
and white triangles. This is equivalent to the statement that the associated
map $f:\Sigma\to T$ has topological degree $0$. I learned this proof from
Kasra Rafi.

We equip $\mbox{\boldmath{$R$}}^{2}$ with the unit equilateral triangulation.
Let $\pi:\mbox{\boldmath{$R$}}^{2}\to T$ be the branched covering which maps
triangles to triangles in an isometric way. A good triangulation has the
property that, around each vertex, the number of black triangles is congruent
mod $3$ to the number of white triangles. In the case of an even
triangulation, a good coloring has the stronger property that around each
vertex the number of black triangles is congruent mod $6$ to the number of
white triangles. But this means that the map $f:\Sigma\to T$ lifts to a map
$\widetilde{f}:\Sigma\to\mbox{\boldmath{$R$}}^{2}$ such that
$f=\pi\circ\widetilde{f}$. The map $\widetilde{f}$ is homotopic to a point and
hence so is $f$. But then $f$ has topological degree $0$.

###  3.2 Asymptotic Properties

In this section we will prove Theorem 1.1. Recall that $\cal S$ is the set of
rational numbers in $(0,1]$. Now suppose that $\\{p_{n}/q_{n}\\}$ is an
infinite sequence of elements of $\cal S$ having an irrational limit $\zeta$.

Statement 1: Let $G(p_{n}/q_{n})$ denote the sequence of rationals we get by
starting with $p_{n}/q_{n}$, iteratively applying the slow Gauss map, then
listing the terms in reverse order. For instance,

$G(3/7)=\frac{1}{1},\hskip 10.0pt\frac{1}{2},\hskip 10.0pt\frac{1}{3},\hskip
10.0pt\frac{3}{4},\hskip 10.0pt\frac{3}{7}.$

###### Lemma 3.1

For any $D$ there are constants $M,N$ such that if $n>N$ then all but the
first $M$ terms of $G(p_{n}/q_{n})$ have $p_{n}>D$.

Proof: Our sequences stabilize in the following sense. For any given $M$, we
can take $N$ sufficiently large so that the first $M$ terms of
$G(p_{n}/q_{n})$ are the same as long as $n>N$. What makes it work is that the
thinner sequence of continued fraction approximants of $p_{n}/q_{n}$ converges
to the sequence of continued fraction approximants of $\zeta$, and we can
derive the $G$-sequences from these thinner sequences.

We also note a second property of our sequences: The numerators of the terms
in $G(p_{n}/q_{n})$ are monotone increasing as we move along the sequence.
When we combine the increasing numerator property with the stabilization
property, we get the result of this lemma. $\spadesuit$

In terms of the flowers, Lemma 3.1 says that all but the first $M$ inner
trapezoid necklaces $Q$ have the property that

$\frac{p(Q)}{A(Q)}<\frac{100}{D}.$

Here $p(Q)$ denotes the perimeter of $Q$ and $A(Q)$ denotes the number of
equilateral triangles comprising $Q$. We picked an unrealistically large
constant of $100$ here to avoid having to think about the fine points of
trapezoids.

Our analysis shows that, within the $n$th flower, the average ratio of the
perimeter of a trapezoid to the area of the trapezoid tends to $0$ as
$n\to\infty$. This immediately implies that the ratio $f_{n}/F_{n}$ converges
to $0$.

Statement 2: Recall that the quadratic irrational limit $\zeta=\lim
p_{n}/q_{n}$ has an eventually periodic continued fraction expansion and
(equivalently) is pre-periodic under the action of the slow Gauss map.

We think of ${\cal T\/}(p_{n}+q_{n}\alpha)$ as a coloring of a doubled
equilateral triangle. We then scale the metric by a factor of $q_{n}^{-1}$.
The corresponding sequence of doubled equilateral triangles converges (say, in
the Gromov-Hausdorff topology) to another doubled equilateral triangle, namely
$\mbox{\boldmath{$C$}}/G_{\beta}$ where $\beta=\zeta+\alpha.$ Again,
$G_{\beta}$ is the group generated by order $3$ rotations in points of
$\beta{\cal E\/}$.

The rescaled colorings also converge. The limiting coloring is made from
“infinite flowers” and parallelograms. The infinite flowers are limits of the
rescaled flowers associated to the Eisenstein integers $a_{n}+b_{n}\alpha$.
Scaling appropriately, we arrange that one of the outer trapezoids in the
infinite flower $F$ has aspect ratio $\zeta$, top right vertex $\beta$ and
horizontal top and bottom. The remaining trapezoids have aspect ratios which
we find by applying the slow Gauss map iteratively to $\zeta$. These necklaces
converge to the origin.

Let $F[k]$ denote the infinite flower obtained by trimming off the outermost
$k$ trapezoid necklaces of $F$. Given the preperiodicity of the slow Gauss map
on $\zeta$, there are integers $m,n$ and some $\lambda\in(0,1)$ such that

$F[m+kn]=\lambda^{k}F[m],\hskip 30.0ptk=1,2,3,...$ (7)

In other words, if we strip off the outer $m$ layers of $F$ then the resulting
infinite flower is self-similar with “period” $n$ and similarity factor
$\lambda$.

The area of a unit equilateral triangle is $\sqrt{3}/4$ and the side length is
$1$. Let us redefine the Eisenstein isoperimetric ratio to be the quantity

$\frac{{\rm perimeter\/}^{2}}{{\rm area\/}}\times\frac{4}{\sqrt{3}}.$ (8)

This new definition coincides with the old definition for colorings based on
unit equilateral triangulations. Also, the new definition is scale invariant.
Thus, to prove Statement 2 of Theorem 1.1 we just need to show that this
quantity is finite and well-defined for our limiting coloring. This suffices
because the invariant then varies continuously.

We first compute the area. This is given by

${\rm
area\/}=C_{1}+C_{2}\sum_{k=1}^{\infty}\lambda^{2k}=C_{1}+\frac{C_{2}}{1-\lambda^{2}}.$

Here $C_{1}$ is a constant that depends on the $m$ outer layers of the
infinite flower and on the triangular regions defining the cap of the flower
$F$. The constant $C_{2}$ is determined by the outer $n$ layers of $F[m]$.

Now we compute the perimeter. This is given by

${\rm
perimeter\/}=C_{3}+C_{4}\sum_{k=1}^{\infty}\lambda^{k}=C_{3}+\frac{C_{4}}{1-\lambda}$

The constants $C_{3},C_{4}$ have a similar dependence as $C_{1},C_{2}$. So,
the quantity in Equation 8 exists and is finite. This completes the proof of
Statement 2.

Remarks:
(1) The quantities $C_{1}\sqrt{3}$ and $C_{2}\sqrt{3}$ both belong to
$\mbox{\boldmath{$Q$}}(\zeta)$. Likewise $C_{3},C_{4},\lambda$ also all belong
to $\mbox{\boldmath{$Q$}}(\zeta)$. Therefore, the limiting value $\eta(\zeta)$
lies in $\mbox{\boldmath{$Q$}}(\zeta)$. I will give some calculations below.
(2) Our insistence that $\\{p_{n}/q_{n}\\}$ be the sequence of continued
fraction approximants of $\zeta$ is more restrictive than need be. The
limiting argument works as long as $\\{p_{n}/q_{n}\\}$ limits to $\zeta$ and
the corresponding continued fraction expansions are uniformly bounded. Thus,
the Eisenstein isoperimetric ratio is well-defined for any irrational in
$(0,1)$ with bounded continued fraction approximation.

###  3.3 Some Calculations

Let us first establish Equation 3. Rather than take the general approach from
the last section we work more concretely with the sequence
$\\{a_{n}/a_{n+1}\\}$ of continued fraction approximants to $\phi^{-1}$. Here

$a_{1},a_{2},a_{3},a_{4},a_{5},...1,1,2,3,5,...$

is the sequence of Fibonacci numbers. We will use the well-known asymptotic
formula

$a_{n}\sim\frac{\phi^{n}}{\sqrt{5}}.$ (9)

For $n\geq 2$ let $f_{n}$ denote the fold count of ${\cal C\/}(a_{n}/a_{n+1})$
and let $F_{n}$ denote the number of triangles. From our program we compute
the following table:

$n$ | $a_{n}$ | $a_{n+1}$ | $f_{n}$ | $F_{n}$ | $\phi^{-6}f_{n}^{2}/F_{n}$
---|---|---|---|---|---
2 | 1 | 2 | 13 | 14 | .672718…
3 | 2 | 3 | 23 | 38 | .775795…
4 | 3 | 5 | 39 | 98 | .864923…
5 | 5 | 8 | 65 | 258 | .912601…
6 | 8 | 13 | 107 | 674 | .946633…

After a little trial and error we find the following formulas

$f_{n}=-1+2\sum_{k=1}^{n+2}a_{k},\hskip
30.0ptF_{n}=2+4\sum_{k=1}^{n}a_{k}a_{k+1}.$ (10)

These formulas give the same answers as in the table above for $n=2,3,4,5,6$.
An easy inductive proof, which we omit, establishes them. Using the
approxiation in Equation 9, and the familiar formula for the partial sums of a
geometric series, and the fact that $1+\phi=\phi^{2}$, we find that

$f_{n}^{2}\approx\frac{4}{5}\times\phi^{2n+8},\hskip
30.0ptF_{n}\approx\frac{4}{5}\times\phi^{2n+2}.$

Here $\approx$ means equal up to a uniformly bounded error. Dividing the one
equation by the other gives Equation 3.

Now we describe some additional (nonrigorous) calculations we did in
Mathematica [Wo]. Starting with a quadratic irrational $\zeta$ we do the
following.

  1. 1.

We take a close continued fraction approximation $p/q$ to $\zeta$. For our
calculations we used the command Rationalize[$\zeta$,Power[10,-1000]]. This
gives us a continued fraction approximant which agrees with $\zeta$ up to
$1000$ decimal places. (We needed roughly this much accuracy in a few cases.)

  2. 2.

We compute the continued fraction expansion of $\eta(p+q\alpha)$.

  3. 3.

We extract what appears to be the start of a preperiodic continued fraction
expansion for a quadratic irrational and we then reconstruct this quadratic
irrational from the (implied) preperiodic continued fraction expansion. (In
all cases, the fractional part of the expression was strictly periodic.)

  4. 4.

After finding what appears to be the period of the continued fraction
expansion, we reconstruct the quadratic irrational which has this continued
fraction expansion. We guess that this is probably $\eta(\zeta)$.

Here we show some examples. Let $\zeta_{n}=\sqrt{n}-{\rm floor\/}(\sqrt{n}).$
We have

$\begin{matrix}\eta(\zeta_{2})&=&\frac{75+53\sqrt{2}}{7}&&\eta(\zeta_{3})&=&\frac{132+72\sqrt{3}}{13}\cr\cr\eta(\zeta_{5})&=&\frac{321+137\sqrt{5}}{19}&&\eta(\zeta_{6})&=&\frac{27+9\sqrt{6}}{2}\cr\cr\eta(\zeta_{7})&=&\frac{3100+856\sqrt{7}}{259}&&\eta(\zeta_{8})&=&\frac{1569+370\sqrt{8}}{98}\end{matrix}$
(11)

One could likely adapt the above proof of Statement 2 of Theorem 1.1 to
rigorously justify these calculations.

###  3.4 Evidence for the Isoperimetric Inequality

Most of our evidence for Conjecture 1.3 comes from calculations within the
famiy of continued fraction colorings. Given primitive Eisenstein integers

$\beta=a+b\alpha,\hskip 30.0pt\beta^{\prime}=a^{\prime}+b^{\prime}\alpha,$

we write $\beta\preceq\beta^{\prime}$ if $b\leq b^{\prime}$. It seems that

$\eta({\cal C\/}(\beta))<\eta({\cal C\/}(\beta^{\prime}))$ (12)

whenever $\beta\preceq\beta^{\prime}$ and $\beta$ is a Fibonacci Eisenstein
integer and $\beta^{\prime}\not=\beta$.

I checked Equation 12 when $\beta$ is any of the first $10$ examples and for
all $|\beta^{\prime}|<500$. I think that this is very strong evidence. The
proof of Equation 12 in general should be purely a matter of number theory. I
haven’t yet looked for a proof. Equation 12 would establish the Eisenstein
Isoperimetric Inequality for the continued fraction colorings. These, of
course, are only a tiny fraction of the good colorings.

The only other evidence I have is the fact that ${\cal C\/}(1+2\alpha)$ and
${\cal C\/}(2+3\alpha)$ seem to minimize the fold counts for good colorings of
${\cal T\/}(1+2\alpha)$ and ${\cal T\/}(2+3\alpha)$ respectively. My program
is not good enough to convincingly check this for larger Fibonacci
triangulations. Combining this scant evidence with the very good evidence for
Equation 12, I make the following conjecture.

###### Conjecture 3.2

Suppose that $\beta$ is a Fibonacci Eisenstein integer and that
$\beta^{\prime}\in(0,1)$ is a different Eisenstein integer such that
$\beta\preceq\beta^{\prime}$. Let ${\cal C\/}={\cal C\/}(\beta)$. Let ${\cal
C\/}^{\prime}$ be an arbitrary good coloring of ${\cal T\/}(\beta^{\prime})$.
Then we have $\eta({\cal C\/})<\eta({\cal C\/}^{\prime})$.

This conjecture would combine with Equation 3 to prove Conjecture 1.3.

It is worth pointing out that that the continued fraction colorings are far
from the best in many cases. Figure 9 compares the continued fraction ${\cal
C\/}(1+5\alpha)$ (left) with another coloring of ${\cal T\/}(1+5\alpha)$
(right) which seems to be the one which minimizes the fold count.

Figure 9: Two good colorings of ${\cal T\/}(1+5\alpha)$.

##  4 A Bound on the Isoperimetric Ratio

In this chapter we prove Theorem 1.2. We first establish an isoperimetric
inequality for a special kind of polygon and then we give the main argument.

###  4.1 Special Hexagons

Say that a special hexagon is a convex hexagon whose interior angles are all
$2\pi/3$. The regular hexagon is an example, and all other special hexagons
are obtained from the regular one by pushing the sides in and out parallel to
themselves. Our first result is a version of the isoperimetric inequality for
special polygons. This result is undoubtedly well-known.

###### Lemma 4.1

The length and area of a special hexagon satisfy the inequality

$\frac{{\rm length\/}^{2}}{{\rm area\/}}\geq 8\sqrt{3}.$ (13)

Proof: It is an elementary exercise, and it is also discussed at length in
[T], that the area of such a hexagon is a quadratic function of the side
lengths $\ell_{1},...,\ell_{6}$. By symmetry, the desired function is
symmetric in the arguments. Therefore, we have

${\rm area\/}=a(\ell_{1}+...+\ell_{6})^{2}+b(\ell_{1}^{2}+...+\ell_{6}^{2}).$

Considering the unit regular hexagon and the unit equilateral triangle, which
is a limiting case, we get the relations

$36a+6b=\frac{3\sqrt{3}}{2},\hskip 30.0pt9a+3b=\frac{\sqrt{3}}{4}.$

Solving these equations leads to the formula

${\rm
area\/}=\frac{1}{6\sqrt{3}}(\ell_{1}+...+\ell_{6})^{2}-\frac{1}{4\sqrt{3}}(\ell_{1}^{2}+...+\ell_{6}^{2}).$
(14)

If we hold the perimiter fixed, we maximize the area by minimizing the sum of
the squares of the lengths. This happens when all lengths are equal, and the
ratio of interest is scale-invariant. Plugging in $\ell_{1}=...=\ell_{6}=1$
and calculating, we get the advertised inequality. $\spadesuit$

###  4.2 The Main Argument

We define an Eisenstein polygon to be a convex polygon whose sides are
contained in the $1$-skeleton of the unit equilateral triangulation. Up to
scaling, Eisenstein polygons are all limits of the special hexagons considered
in the last section. Let $f(P)$ denote the perimeter of an Eisenstein polygon
and let $F(p)$ denote the number of triangles it contains. As an immediate
consequence of Lemma 4.1, we have

$\frac{f^{2}(P)}{F(P)}\geq 6.$ (15)

Let $\cal C$ be a good coloring of some triangulation $\cal T$ with degree
sequence $6,...,6,2,2,2$. Let $f$ denote the fold count and let $F$ be the
number of faces. Our goal is to show that $\eta({\cal C\/})=f^{2}/F\geq 3$.
Note that $\cal C$ partitions $\cal T$ into a finite number of monochrome
regions with connected interior.

###### Lemma 4.2

Each monochrome region is isometric to an Eisenstein polygon.

Proof: Let $P$ be such a region. Without loss of generality assume that $P$ is
colored white. To make the argument clearer, we shave off the outer $\epsilon$
of $P$, so that its boundary does not self-intersect. Let $P_{\epsilon}$ be
this slightly smaller polygon. Since both colors occur at the triangles
touching each degree $2$ vertex, we see that $P_{\epsilon}$ does not contain
any degree $2$ vertices. Hence $P_{\epsilon}$ is locally Eucidean.

Consider $\partial P_{\epsilon}$. Each vertex $v_{\epsilon}$ of $\partial
P_{\epsilon}$ is within $\epsilon$ of a unique vertex $v$ of $P$. Because $P$
comes from a good coloring, $v$ has at most $3$ white triangles around it.
Hence $P_{\epsilon}$ is locally convex near each boundary component.

Consider a lift $\widetilde{P}_{\epsilon}$ of $P_{\epsilon}$ to $C$, the
orbifold universal cover of our flat cone sphere. This lift is also locally
convex near its boundary components. If $\widetilde{P}_{\epsilon}$ is
unbounded then the local convexity near the boundary forces it to be an
infinite strip. But then $P_{\epsilon}$ is an annulus with geodesic boundary.
This is impossible in our flat cone sphere. Hence $\widetilde{P}_{\epsilon}$
is bounded. The local convexity forces $\widetilde{P}_{\epsilon}$ to have just
one boundary component. If the map $\widetilde{P}_{\epsilon}\to P_{\epsilon}$
is not a global isometry then $P_{\epsilon}$ contains some degree $2$
vertices, a contradiction. We conclude that $\widetilde{P}_{\epsilon}$ is a
convex polygon and the map $\widetilde{P}_{\epsilon}\to P_{\epsilon}$ is an
isometry. Hence $P_{\epsilon}$ is a convex polygon.

Letting $\epsilon\to 0$ we see that $P$ is also a convex polygon. But then $P$
is also an Eisenstein polygon. $\spadesuit$

Let $P_{1},...,P_{k}$ be the white connected regions. By Lemma 4.2, each
$P_{j}$ is an Eisenstein polygon. Let $f_{j}=f(P_{j})$ and $F_{j}=F(P_{j})$.
We have

$\min_{j}\frac{f_{j}^{2}}{F_{j}}\geq 6,\hskip 30.0ptf=f_{1}+...+f_{k},\hskip
30.0pt\frac{F}{2}=F_{1}+...+F_{k}.$ (16)

The middle equality comes from the fact that each black-white interface in
particular lies in the boundary of some $P_{j}$, and that $\partial P_{i}$ and
$\partial P_{j}$ are disjoint except perhaps for vertex intersections when
$i\not=j$. Hence

$\frac{2f^{2}}{F}=\frac{(f_{1}+...+f_{k})^{2}}{F/2}\geq\frac{f_{1}^{2}+...+f_{k}^{2}}{F/2}=\frac{f_{1}^{2}}{F_{1}}\oplus...\oplus\frac{f_{k}^{2}}{F_{k}}\geq
6.$ (17)

Here $\oplus$ denotes the Farey sum: We add the numerators and we add the
denominators. As is well known, the Farey sum of some fractions lies between
the minimum and the maximum of the fractions.

##  5 References

[T], W. P. Thurston, Shapes of polyhedra and triangulations of the sphere,
Geometry and Topology monographs 1: pp 511–549 (1998)

[W], D. B. West, Introduction to Graph Theory, 2nd Ed., Prentice-Hall (2000)

[Wo] S. Wolfram, Mathematica (2020) wolfram.com/mathematica.


#  An Algorithm for the Constrained Longest Common Subsequence and Substring
Problem

Rao Li
Dept. of Computer Science, Engineering, and Mathematics
University of South Carolina Aiken
Aiken, SC 29801
USA
Email<EMAIL_ADDRESS>Jyotishmoy Deka
Dept. of Electrical Engineering
Tezpur University
Tezpur, Assam 784028
India
Email<EMAIL_ADDRESS>Kaushik Deka
Dept. of Computer Science and Engineering
National Institute of Technology Silchar
Cachar, Assam 788010
India
Email<EMAIL_ADDRESS>Dorothy Li
12000 Market Street, Unit 63
Reston, VA 20190
USA
Email<EMAIL_ADDRESS>
(Aug. 1, 2023)

###### Abstract

Let $\Sigma$ be an alphabet. For two strings $X$, $Y$, and a constrained
string $P$ over the alphabet $\Sigma$, the constrained longest common
subsequence and substring problem for two strings $X$ and $Y$ with respect to
$P$ is to find a longest string $Z$ which is a subsequence of $X$, a substring
of $Y$, and has $P$ as a subsequence. In this paper, we propose an algorithm
for the constrained longest common subsequence and substring problem for two
strings with a constrained string.

Keywords: longest common subsequence, longest
common substring, longest common
subsequence and substring, constrained
longest common subsequence

1\. Introduction

Let $\Sigma$ be an alphabet and $S$ a string over $\Sigma$. A subsequence of a
string $S$ over an alphabet $\Sigma$ is obatined by deleting zero or more
letters of $S$. A substring of a string $S$ is a subsequence of $S$ consists
of consecutive letters in $S$. The longest common subsequence problem (LCSSeq)
for two strings is to find a longest string which is a subsequence of both
strings. The longest common substring (LCSStr) problem for two strings is to
find a longest string which is a substring of both strings. Both the longest
common subsequence problem and the longest common substring problem have been
well-studied in last several decades. More details on the studies for the
first problem can be found in [1], [2], [4], [6], [7], [8], [9], and [11] and
the second problem can be found in [3] and [13].

Tsai [12] extended the longest common subsequence problem for two strings to
the constrained longest common subsequence (CLCSSeq) probelm for two strings.
For two strings $X$, $Y$, and a constrained string $P$, the constrained
longest common subsequence problem for two strings $X$ and $Y$ with respect to
$P$ is to find a string $Z$ such that $Z$ is a longest common subsequence for
$X$ and $Y$ and $P$ is a subsequence of $Z$. Tsai [12] designed an
$O(|X|^{2}|Y|^{2}|P|)$ time algorithm for the CLCSSeq problem for two strings,
where $|X|$, $|Y|$, and $|P|$ denote the lengths of the strings $X$, $Y$, and
$P$, respectively. Chin et al. [5] improved Tsai’s algorithm and designed an
$O(|X||Y||P|)$ time algorithm for the CLCSSeq problem for two strings $X$ and
$Y$ and a constrained string $P$.

Motivated by LCSSeq and LCSStr problems, Li et. al [10] introduced the longest
common subsequence and substring (LCSSeqSStr) problem for two strings. For two
strings $X$, $Y$, the longest common subsequence and substring problem for $X$
and $Y$ is to find a longest string which is a subsequence of $X$ and a
substring of $Y$. They also designed an $O(|X||Y|)$ time algorithm for
LCSSeqSStr problem for two strings $X$ and $Y$ in [10].

Motivated by Tsai’s extension of LCSSeq to CLCSSeq for two strings, we
introduce the constrained longest common subsequence and substring problem for
two strings with respect to a constrained string. For two strings $X$, $Y$,
and a constrained string $P$, the constrained longest common subsequence and
substring (CLCSSeqSStr) problem for two strings $X$ and $Y$ with respect to
$P$ is to find a string $Z$ such that $Z$ is a longest common subsequence of
$X$, a substring of $Y$, and has $P$ as a subsequence. Clearly, the CLCSSeq
problem is a special CLCSSeqSStr problem with an empty constrained string. In
this paper, we, using some ideas and techniques developed in [5], design an
$O(|X||Y||P|)$ time algorithm for CLCSSeqSStr problem for two strings and a
constrained string.

2\. The Recursions in the Algorithm

In order to present our algorithm, we need to establish some recursions to be
used in our algorithm. Before establishing the recursions, we need some
notations as follows. For a given string $S=s_{1}s_{2}...s_{l}$ over an
alphabet $\Sigma$, the size of $S$, denoted $|S|$, is defined as the number of
letters in $S$. The $i$ prefix of $S$ is defined as
$S_{i}=s_{1}s_{2}...s_{i}$, where $1\leq i\leq l$. Conventionally, $S_{0}$ is
defined as an empty string. The $l$ suffixes of $S$ are the strings of
$s_{1}s_{2}...s_{l}$, $s_{2}s_{3}...s_{l}$, …, $s_{l-1}s_{l}$, and $s_{l}$.
Let $X=x_{1}x_{2}...x_{m}$ and $Y=y_{1}y_{2}...y_{n}$ be two strings and
$P=p_{1}p_{2}...p_{r}$ a constrained string. We define $Z[i,j,k]$ as a string
satisfying the following conditions, where $1\leq i\leq m$, $1\leq j\leq n$,
and $1\leq k\leq r$,

($1$) it is a subsequence of $X_{i}$,
($2$) it is a suffix of $Y_{j}$,
($3$) it has $P_{k}$ as a subsequence,
($4$) under ($1$), ($2$) and (3), its length is as large as possible.

Claim $1$. Let $U^{k}=u_{1}^{k}u_{2}^{k}...u_{h_{k}}^{k}$ be a longest string
which is a subsequence of $X$, a substring of $Y$, and has $P_{k}$ as a
subsequence. Then $h_{k}=\max\\{\,|Z[i,j,k]|:1\leq i\leq m,1\leq j\leq n,1\leq
k\leq r\,\\}$.

Proof of Claim $1$. For each $i$ with $1\leq i\leq m$, each $j$ with $1\leq
j\leq n$, and each $k$ with $1\leq k\leq r$, we, from the definition of
$Z[i,j,k]$, have that $Z[i,j,k]$ is a subsequence of $X$, a substring of $Y$,
and has $P_{k}$ as a subsequence. By the definition of $U^{k}$, we have that
$|Z[i,j,k]|\leq|U^{k}|=h_{k}$. Thus $\max\\{\,|Z[i,j,k]|:1\leq i\leq m,1\leq
j\leq n,1\leq k\leq r\,\\}\leq h_{k}$.

Since $U^{k}=u_{1}^{k}u_{2}^{k}...u_{h_{k}}^{k}$ is a longest string which is
a subsequence of $X$, a substring of $Y$, and has $P_{k}$ as a subsequence,
there is an index $s$ and an index $t$ such that $u_{h_{k}}^{k}=x_{s}$ and
$u_{h_{k}}^{k}=y_{t}$ such that $U^{k}=u_{1}^{k}u_{2}^{k}...u_{h_{k}}^{k}$ is
a subsequence of $X_{s}$, a suffix of $Y_{t}$, and has $P_{k}$ as a
subsequence. From the definition of $Z[i,j,k]$, we have that
$h_{k}\leq|Z[s,t,k]|\leq\max\\{\,|Z[i,j,k]|:1\leq i\leq m,1\leq j\leq n,1\leq
k\leq r\,\\}$.

Hence $h_{k}=\max\\{\,|Z[i,j,k]|:1\leq i\leq m,1\leq j\leq n,1\leq k\leq
r\,\\}$ and the proof of Claim $1$ is complete.

Claim $2$. Suppose that $X_{i}=x_{1}x_{2}...x_{i}$,
$Y_{j}=y_{1}y_{2}...y_{j}$, and $P=p_{1}p_{2}...p_{k}$, where $1\leq i\leq m$
and $1\leq j\leq n$, $1\leq k\leq r$. If $Z[i,j,k]=z_{1}z_{2}...z_{a}$ is a
string satisfying conditions ($1$), ($2$), ($3$), and ($4$) above. Then we
have only the following possible cases and the statement in each case is true.

Case $1$. $x_{i}=y_{j}=p_{k}$. We have $|Z[i,j,k]|=|Z[i-1,j-1,k-1]|+1$ in this
case.

Case $2$. $x_{i}=y_{j}\neq p_{k}$. We have $|Z[i,j,k]|=|Z[i-1,j-1,k]|+1$ in
this case.

Case $3$. $x_{i}\neq y_{j}$, $x_{i}\neq p_{k}$, and $y_{j}=p_{k}$. We have
$|Z[i,j,k]|=|Z[i-1,j,k||$ in this case.

Case $4$. $x_{i}\neq y_{j}$, $x_{i}\neq p_{k}$, and $y_{j}\neq p_{k}$. We have
$|Z[i,j,k]|=|Z[i-1,j,k||$ in this case.

Case $5$. $x_{i}\neq y_{j}$, $x_{i}=p_{k}$, and $y_{j}\neq p_{k}$. This case
does not happen.

Proof of Claim $2$. The five cases can be figured out in the following way.
Firstly, we have two cases of $x_{i}=y_{j}$ or $x_{i}\neq y_{j}$. When
$x_{i}=y_{j}$, we just can have two possible cases of $x_{i}=y_{j}=p_{k}$ or
$x_{i}=y_{j}\neq p_{k}$. When $x_{i}\neq y_{j}$, we just can have three
possible cases of $x_{i}\neq p_{k}$ and $y_{j}=p_{k}$, $x_{i}\neq p_{k}$ and
$y_{j}\neq p_{k}$, or $x_{i}=p_{k}$ and $y_{j}\neq p_{k}$. Next we will prove
the statements in the five cases.

Case $1$. Since $Z[i,j,k]=z_{1}z_{2}...z_{a}$ is a suffix of $Y_{j}$, we have
that $z_{a}=y_{j}=x_{i}=p_{k}$. Let $W=w_{1}w_{2}...w_{b}=Z[i-1,j-1,k-1]$ be a
string satisfying the following conditions,

\- it is a subsequence of $X_{i-1}$.
\- it is a suffix of $Y_{j-1}$,
\- it has $P_{k-1}$ as a subsequence,
\- under ($1$), ($2$) and (3), its length is as large as possible.

Note that $z_{1}z_{2}...z_{a-1}$ is a string which is a subsequence of
$X_{i-1}$, a suffix of $Y_{j-1}$, and has $P_{k-1}$ as a subsequence. By the
definition of $W=w_{1}w_{2}...w_{b}$, we have that $a-1\leq b$. Namely, $a\leq
b+1$.

Note that $w_{1}w_{2}...w_{b}z_{a}$ is a string satisfying following
conditions,

\- it is a subsequence of $X_{i}$,
\- it is a suffix of $Y_{j}$,
\- it has $P_{k}$ as a subsequence.

By the definition of $Z[i,j,k]=z_{1}z_{2}...z_{a}$, we have that $b+1\leq a$.
Thus $a=b+1$ and $|Z[i,j,k]|=|Z[i-1,j-1,k-1]|+1$.

Case $2$. Since $Z[i,j,k]=z_{1}z_{2}...z_{a}$ is a suffix of $Y_{j}$, we have
that $z_{a}=y_{j}=x_{i}\neq p_{k}$. Let $U=u_{1}u_{2}...u_{c}=Z[i-1,j-1,k]$ be
a string satisfying the following conditions,

\- it is a subsequence of $X_{i-1}$,
\- it is a suffix of $Y_{j-1}$,
\- it has $P_{k}$ as a subsequenc,
\- under ($1$), ($2$) and (3), its length is as large as possible.

Note that $z_{1}z_{2}...z_{a-1}$ is a string which is a subsequence of
$X_{i-1}$, a suffix of $Y_{j-1}$, and has $P_{k}$ as a subsequence. By the
definition of $U=u_{1}u_{2}...u_{c}=Z[i-1,j-1,k]$, we have that $a-1\leq c$.
Namely, $a\leq c+1$.

Note that $u_{1}u_{2}...u_{c}$ is a string satisfying the following
conditions,

\- it is a subsequence of $X_{i-1}$,
\- it is a suffix of $Y_{j-1}$,
\- it has $P_{k}$ as a subsequence.

Thus $u_{1}u_{2}...u_{c}y_{j}$ is a string which is a subsequence of $X_{i}$,
a suffix of $Y_{j}$, and has $P_{k}$ as a subsequence. By the definition of
$Z[i,j,k]=z_{1}z_{2}...z_{a}$, we have that $c+1\leq a$. Thus $a=c+1$ and
$|Z[i,j,k]|=|Z[i-1,j-1,k]|+1$.

Case $3$. Since $Z[i,j,k]=z_{1}z_{2}...z_{a}$ is a suffix of $Y_{j}$, we have
that $z_{a}=y_{j}=p_{k}\neq x_{i}$. Let $V=v_{1}v_{2}...v_{d}=Z[i-1,j,k]$ be a
string satisfying the following conditions,

\- it is a subsequence of $X_{i-1}$,
\- it is a suffix of $Y_{j}$,
\- it has $P_{k}$ as a subsequence,
\- under ($1$), ($2$) and (3), its length is as large as possible.

Note that $z_{1}z_{2}...z_{a}$ is a string which is a subsequence of
$X_{i-1}$, a suffix of $Y_{j}$, and has $P_{k}$ as a subsequence. By the
definition of $V=v_{1}v_{2}...v_{d}=Z[i-1,j,k]$, we have that $a\leq d$.

Note that $v_{1}v_{2}...v_{d}$ is a string satisfying conditions,

\- it is a subsequence of $X_{i-1}$,
\- it is a suffix of $Y_{j}$,
\- it has $P_{k}$ as a subsequence.

Thus $v_{1}v_{2}...v_{d}$ is a string which is a subsequence of $X_{i}$, a
suffix of $Y_{j}$, and has $P_{k}$ as a subsequence. By the definition of
$Z[i,j,k]=z_{1}z_{2}...z_{a}$, we have that $d\leq a$. Thus $a=d$ and
$|Z[i,j,k]|=|Z[i-1,j,k]|$.

Case $4$. Since $Z[i,j,k]=z_{1}z_{2}...z_{a}$ is a suffix of $Y_{j}$, we have
that $z_{a}=y_{j}\neq p_{k}$, $z_{a}=y_{j}\neq x_{i}$, and $x_{i}\neq p_{k}$.
Let $Q=q_{1}q_{2}...q_{e}=Z[i-1,j,k]$ be a string satisfying the following
conditions,

\- it is a subsequence of $X_{i-1}$,
\- it is a suffix of $Y_{j}$,
\- it has $P_{k}$ as a subsequence,
\- under ($1$), ($2$) and (3), its length is as large as possible.

Note that $z_{1}z_{2}...z_{a}$ is a string which is a subsequence of
$X_{i-1}$, a suffix of $Y_{j}$, and has $P_{k}$ as a subsequence. By the
definition of $Q=q_{1}q_{2}...q_{e}=Z[i-1,j,k]$, we have that $a\leq e$.

Note that $q_{1}q_{2}...q_{e}$ is a string satisfying the following
conditions,

\- it is a subsequence of $X_{i-1}$,
\- it is a suffix of $Y_{j}$,
\- it has $P_{k}$ as a subsequence.

Thus $q_{1}q_{2}...q_{e}$ is a string which is a subsequence of $X_{i}$, a
suffix of $Y_{j}$, and has $P_{k}$ as a subsequence. By the definition of
$Z[i,j,k]=z_{1}z_{2}...z_{a}$, we have that $e\leq a$. Thus $a=e$ and
$|Z[i,j,k]|=|Z[i-1,j,k]|$.

Case $5$. Since $Z[i,j,k]=z_{1}z_{2}...z_{a}$ is a suffix of $Y_{j}$, we have
that $z_{a}=y_{j}\neq x_{i}=p_{k}$. Since $z_{1}z_{2}...z_{a}$ is a
subsequence of $X_{i}$ and $x_{i}\neq z_{a}$, we have that $z_{a}$ appears
before $x_{i}$ on $X_{i}$. Since $x_{i}=p_{k}$ on $X_{i}$,
$p_{1}p_{2}...p_{k}$ cannot be a subsequence of $z_{1}z_{2}...z_{a}$, a
conradiction. Note that since this case does not happen, we will not deal with
this case in our algorithm.

Therefore the proof of Claim $2$ is complete.

The following Claim $3$ which will used in our algorithm demonstrates the
implications of the condition that there is not a string which is a
subsequence of $X_{i}=x_{1}x_{2}...x_{i}$, a suffix of
$Y_{j}=y_{1}y_{2}...y_{j}$, and has $P_{k}=p_{1}p_{2}...p_{k}$ as a
subsequence.

Claim $3$. Suppose there is not a string which is a subsequence of
$X_{i}=x_{1}x_{2}...x_{i}$, a suffix of $Y_{j}=y_{1}y_{2}...y_{j}$, and has
$P_{k}=p_{1}p_{2}...p_{k}$ as a subsequence.

[$1$]. If $x_{i}=y_{j}=p_{k}$, then there is not a string which is a
subsequence of $X_{i-1}=x_{1}x_{2}...x_{i-1}$, a suffix of
$Y_{j-1}=y_{1}y_{2}...y_{j-1}$, and has $P_{k-1}=p_{1}p_{2}...p_{k-1}$ as a
subsequence.

[$2$]. If $x_{i}=y_{j}\neq p_{k}$, then there is not a string which is a
subsequence of $X_{i-1}=x_{1}x_{2}...x_{i-1}$, a suffix of
$Y_{j-1}=y_{1}y_{2}...y_{j-1}$, and has $P_{k}=p_{1}p_{2}...p_{k}$ as a
subsequence.

[$3$]. If $x_{i}\neq y_{j}$, $x_{i}\neq p_{k}$, and $y_{j}=p_{k}$, then there
is not a string which is a subsequence of $X_{i-1}=x_{1}x_{2}...x_{i-1}$, a
suffix of $Y_{j}=y_{1}y_{2}...y_{j}$, and has $P_{k}=p_{1}p_{2}...p_{k}$ as a
subsequence.

[$4$]. If $x_{i}\neq y_{j}$, $x_{i}\neq p_{k}$, and $y_{j}\neq p_{k}$, then
there is not a string which is a subsequence for
$X_{i-1}=x_{1}x_{2}...x_{i-1}$, a suffix of $Y_{j}=y_{1}y_{2}...y_{j}$, and
has $P_{k}=p_{1}p_{2}...p_{k}$ as a subsequence.

Proof of Claim $3$. We next will prove the statements in the four cases.

[$1$]. Now we have that $x_{i}=y_{j}=p_{k}$. Suppose, to the contrary, that
there is a string $W_{1}$ which is a subsequence of
$X_{i-1}=x_{1}x_{2}...x_{i-1}$, a suffix of $Y_{j-1}=y_{1}y_{2}...y_{j-1}$,
and has $P=p_{1}p_{2}...p_{k-1}$ as a subsequence. Then $W_{1}x_{i}$ is a
string which is a subsequence of $X_{i}=x_{1}x_{2}...x_{i}$, a suffix of
$Y_{j}=y_{1}y_{2}...y_{j}$, and has $P_{k}=p_{1}p_{2}...p_{k}$ as a
subsequence, a contradiction.

[$2$]. Now we have that $x_{i}=y_{j}\neq p_{k}$. Suppose, to the contrary,
that there is a string $W_{2}$ which is a subsequence of
$X_{i-1}=x_{1}x_{2}...x_{i-1}$, a suffix of $Y=y_{1}y_{2}...y_{j-1}$, and has
$P_{k}=p_{1}p_{2}...p_{k}$ as a subsequence. Then $W_{2}x_{i}$ is a string
which is a subsequence of $X_{i}=x_{1}x_{2}...x_{i}$, a suffix of
$Y_{j}=y_{1}y_{2}...y_{j}$, and has $P_{k}=p_{1}p_{2}...p_{k}$ as a
subsequence, a contradiction.

[$3$]. Now we have that $x_{i}\neq y_{j}$, $x_{i}\neq p_{k}$, and
$y_{j}=p_{k}$. Suppose, to the contrary, that there is a string $W_{3}$ which
is a subsequence for $X_{i-1}=x_{1}x_{2}...x_{i-1}$, a suffix of
$Y_{j}=y_{1}y_{2}...y_{j}$, and has $P_{k}=p_{1}p_{2}...p_{k}$ as a
subsequence. Then $W_{3}$ is a string which is a subsequence of
$X_{i}=x_{1}x_{2}...x_{i}$, a suffix of $Y_{j}=y_{1}y_{2}...y_{j}$, and has
$P_{k}=p_{1}p_{2}...p_{k}$ as a subsequence, a contradiction.

[$4$]. Now we have that $x_{i}\neq y_{j}$, $x_{i}\neq p_{k}$, and $y_{j}\neq
p_{k}$. Suppose, to the contrary, that there is a string $W_{4}$ which is a
subsequence of $X_{i-1}=x_{1}x_{2}...x_{i-1}$, a suffix of
$Y_{j}=y_{1}y_{2}...y_{j}$, and has $P_{k}=p_{1}p_{2}...p_{k}$ as a
subsequence. Then $W_{4}$ is a string which is a subsequence of
$X_{i}=x_{1}x_{2}...x_{i}$, a suffix of $Y=y_{1}y_{2}...y_{j}$, and has
$P_{k}=p_{1}p_{2}...p_{k}$ as a subsequence, a contradiction.

Therefore the proof of Claim $3$ is complete.

3\. The Algorithm

Now we can present our algorithm. We assume that $X=x_{1}x_{2}...x_{m}$,
$Y=y_{1}y_{2}...y_{n}$, and $P=p_{1}p_{2}...p_{r}$. Let $M$ be a three
dimensional array of size $(m+1)(n+1)(r+1)$. It can be thought as a collection
of $(r+1)$ two dimensional arrays of size $(m+1)(n+1)$. The cells
$M[i][j][k]$, where $0\leq i\leq m$, $0\leq j\leq n$, and $0\leq k\leq r$,
store the lengths of longest strings such that each of them is a subsequence
of $X_{i}$, a suffix of $Y_{j}$, and has $P_{k}$ as a subsequence.
If either $i<r$ or $j<r$, there is not a string which is a subsequence of
$X_{i}$, a suffix of $Y_{j}$, and has $P_{k}$ as a subsequence. This situation
is represented by setting $M[i][j][k]=-\infty$, where $\infty$ can be any
number which is greater than the larger one between $m$ and $n$. Now we can
fill in some boundary cells in array $M$.

If $i=0$ and $k=0$ or $j=0$ and $k=0$, the length of a string which is a
subsequence of $X_{i}$, a suffix of $Y_{j}$, and has $P_{k}$ as a subsequence
is zero. Thus $M[0][j][0]=0$, where $0\leq j\leq n$ and $M[i][0][0]=0$, where
$0\leq i\leq m$.

If $k=0$ or $P$ is an empty string. The CLCSSeqSStr problem for two strings
$X$ and $Y$ and a constrained string $P$ becomes the LCSSeqSStr problem for
two strings $X$ and $Y$. The cells of $M[i][j][0]$, where $1\leq i\leq m$ and
$1\leq j\leq n$, can be filled in by the following rules. If $x_{i}=y_{j}$,
then $M[i][j]=M[i-1][j-1]+1$. If $x_{i}\neq y_{j}$, then $M[i][j]=M[i-1][j]$.
The detailed proofs for the truth of the rules can be found in [10].

If $i=0$ and $k\geq 1$, there is not a string which is a subsequence of
$X_{i}$, a suffix of $Y_{j}$, and has $P_{k}$ as a subsequence. Thus
$M[0][j][k]=-\infty$, where $0\leq j\leq n$ and $1\leq k\leq r$.

If $j=0$ and $k\geq 1$, there is not a string which is a subsequence of
$X_{i}$, a suffix of $Y_{j}$, and has $P$ as a subsequence. Thus
$M[i][0][k]=-\infty$, where $0\leq i\leq m$ and $1\leq k\leq r$.

Next we will fill in the remaining cells $M[i][j][k]$, where $i\geq 1$, $j\geq
1$, and $k\geq 1$.

If $i\geq 1$, $j\geq 1$, $k\geq 1$, and $x_{i}=y_{j}=p_{k}$, then
$M[i][j][k]=M[i-1][j-1][k-1]+1$.

If $i\geq 1$, $j\geq 1$, $k\geq 1$, and $x_{i}=y_{j}\neq p_{k}$, then
$M[i][j][k]=M[i-1][j-1][k]+1$.

If $i\geq 1$, $j\geq 1$, $k\geq 1$, and $x_{i}\neq y_{j}$, $x_{i}\neq p_{k}$,
and $y_{j}=p_{k}$, then $M[i][j][k]=M[i-1][j][k]$.

If $i\geq 1$, $j\geq 1$, $k\geq 1$, and $x_{i}\neq y_{j}$, $x_{i}\neq p_{k}$,
and $y_{j}\neq p_{k}$, then $M[i][j][k]=M[i-1][j][k]$.

Notice that Claim $1$ implies that if a longest string which is a subsequence
of $X=X_{m}$, a substring of $Y=Y_{n}$, and has $P=P_{r}$ as a subsequence
exists then its length is equal to $\max\\{\,|Z[i,j,r]|:1\leq i\leq m,1\leq
j\leq n\,\\}=\max\\{\,M[i][j][r]:1\leq i\leq m,1\leq j\leq n\,\\}$ . Hence, a
longest string which is a subsequence of $X$, a substring of $Y$, and has $P$
as a subsequence can be found in the following way. Define one variable called
$maxLength$ which eventually represents the length of a longest string which
is a subsequence of $X$, a substring of $Y$, and has $P$ as a subsequence and
its initial value is $0$. Define another variable called $lastIndexOnY$ which
eventually represents the last index of the desired string which is a
substring of $Y$ and its initial value is $n$. Visit all the cells of
$M[i][j][r]$, where $0\leq i\leq m$ and $0\leq j\leq n$, in the last two
dimensional array created in the algorithm above by using a loop embedded
another loop. During the visitation, if $M[i][j][r]>maxLength$, then update
$maxLength$ and $lastIndexOnY$ as $M[i][j][r]$ and $j$, respectively. After
finishing the visitation of all the cells of $M[i][j][r]$, where $0\leq i\leq
m$ and $0\leq j\leq n$, we return the substring of $Y$ between $(lastIndexOnY-
maxLength)$ and $lastIndexOnY$.

The correctness of the above algorithm is ensured by Claim $1$, Claim $2$, and
Claim $3$. It is clear that both time complexity and space complexity of the
above algorithm are $O((m+1)(n+1)(r+1))=O(mnr)$.

We implemented our algorithm in Java and the program can be found at
“https://sciences.usca.edu/math/~mathdept/rli/
CLCSSeqSStr/CLCSubseqSubstr.pdf”.

## References

  * [1] A. Apostolico, String editing and longest common subsequences, in: G. Rozenberg and A. Salomaa (Eds.), Linear Modeling: Background and Application, in: Handbook of Formal Languages, Vol. 2, Springer-Verlag, Berlin, 1997.
  * [2] A. Apostolico, Chapter 13: General pattern matching, in: M. J. Atallah (Ed.), Handbook of Algorithms and Theory of Computation, CRC, Boca Raton, FL, 1998.
  * [3] D. Gusfield, II: Suffix Trees and Their Uses, Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997.
  * [4] L. Bergroth, H. Hakonen, and T. Raita, A survey of longest common subsequence algorithms, in: SPIRE, A Coruña, Spain, 2000.
  * [5] F. Y. L. Chin, A. De Santis, A. L. Ferrara, N. L. Ho, and S. K. Kim, A simple algorithm for the constrained sequence problems, Information Processing Letters 90 (2004) 175-179.
  * [6] T. Cormen, C. Leiserson, and R. Rivest, Section 16.3: Longest common subsequence, Introduction to Algorithms, MIT Press, Cambridge, MA, 1990.
  * [7] D. Hirschberg, A linear space algorithm for computing maximal common subsequences, Communications of the ACM 18 (1975) 341–343.
  * [8] D. Hirschberg, Serial computations of Levenshtein distances, in: A. Apostolico and Z. Galil (Eds.), Pattern Matching Algorithms, Oxford University Press, Oxford, 1997.
  * [9] J. Hunt and T. Szymanski, A fast algorithm for computing longest common subsequences, Communications of the ACM 20 (1977) 350–353.
  * [10] R. Li, J. Deka, and K. Deka, An algorithm for the longest common subsequence and substring problem, manuscript, July 2023. The implementation of the algorithm in Java can be found at “https://sciences.usca.edu/math/~mathdept
/rli/LCSSeqSStr/LCSS.pdf”.

  * [11] C. Rick, New algorithms for the longest common subsequence problem, Research Report No. 85123-CS, University of Bonn, 1994.
  * [12] Y. T. Tsai, The constrained longest common subsequence problem, Information Processing Letters 88 (2003) 173-176.
  * [13] P. Weiner, Linear pattern matching algorithms. In: 14th Annual Symposium on Switching and Automata Theory, Iowa City, Iowa, USA, October 15–17, 1973, pp. 1–11 (1973).