1 Introduction
Given an oriented smooth link L in
$S^3$
, the link group of L, denoted
$\pi (L)$
, is the fundamental group of the complement of L in
$S^3$
. Also, let
$\Delta _L(t)$
denote the Alexander polynomial of L (see [Reference Murasugi23, Chapter 6] for details).
Let
$h:\pi (L)\to H_1(S^3-L)$
be the Hurewicz map, and let
$\varphi :H_1(S^3-L) \to \mathbb{Z}$
be the map defined by identifying the oriented meridians of each component of L with each other. The group
$\pi (L)$
is canonically an extension of
$\mathbb{Z}$
by
$\ker (\varphi \circ h)$
as follows:
We call the subgroup
$\ker (\varphi \circ h)$
the Alexander subgroup of the oriented link L. When L is a knot, the Alexander subgroup is the commutator subgroup of
$\pi (L)$
.
A group G is residually torsion-free nilpotent if for every nontrivial element
$x\in G$
, there is a normal subgroup
$N\lhd G$
such that
$x\notin N$
and
$G/N$
is a torsion-free nilpotent group. The residual torsion-free nilpotence of the Alexander subgroup of a link group has applications to bi-orderability [Reference Linnell, Rhemtulla and Rolfsen13] and ribbon concordance [Reference Gordon10]. Several knots are known to have groups with residually torsion-free nilpotent commutator subgroups including fibered knots (since free groups are residually torsion-free nilpotent [Reference Mal’tsev17] and the commutator subgroup of a fibered knot group is a finitely generated free group), twist knots [Reference Mayland18], all knots in Reidemeister’s knot table (see [Reference Reidemeister26]) except
$8_{13}$
,
$9_{25}$
,
$9_{35}$
,
$9_{38}$
,
$9_{41}$
, and
$9_{49}$
[Reference Mayland18], and pseudo-alternating links whose Alexander polynomials have prime power leading coefficients [Reference Mayland and Murasugi20]. This paper confirms that many two-bridge links, including all two-bridge knots, have groups with residually torsion-free nilpotent Alexander subgroups.
Theorem 1.1 If L is an oriented two-bridge link whose Alexander polynomial has relatively prime coefficients (collectively, not pairwise), then the Alexander subgroup of
$\pi (L)$
is residually torsion-free nilpotent.
Remark 1.2 The condition on the coefficients of the Alexander polynomial cannot be removed. For example, if L is the
$(4,2)$
-torus link, as shown in Figure 1, then L has Alexander subgroup isomorphic to
$$\begin{align*}\langle \{S_i\}_{i\in\mathbb{Z}} \; | \; S_i^2=S_{i+1}^2,i\in\mathbb{Z} \rangle, \end{align*}$$
which is not residually nilpotent. (For details on computing the Alexander subgroup, see Section 3.) The Alexander polynomial of L is
$\Delta _L(t)=2t-2$
.
Figure 1: The
$(4,2)$
-torus link.
It is a well-known fact that
$\Delta _K(1)=\pm 1$
for every knot K [Reference Alexander2]. It follows that the coefficients of the Alexander polynomial of K are relatively prime, so we have the following corollary.
Corollary 1.3 The commutator subgroup of a two-bridge knot group is residually torsion-free nilpotent.
The following conjecture is an analog of a question by Mayland in [Reference Mayland18].
Conjecture 1.4 The Alexander subgroup of a link group of an alternating link is residually torsion-free nilpotent whenever the link’s Alexander polynomial has relatively prime coefficients.
1.1 Summary of the techniques used
The proof of Theorem 1.1 relies on Baumslag’s work on para-free groups [Reference Baumslag3, Reference Baumslag4]. Let G be a group. Define
$\gamma _1G:=G$
, and for each positive integer n, define
$\gamma _{n+1}G:=[G,\gamma _nG]$
. A group G is para-free of rank r if:
-
(1) for some free group F of rank r,
$G/\gamma _nG\cong F/\gamma _n F$
for each n, and -
(2) G is residually nilpotent.
Baumslag provides a sufficient condition for a group to be residually torsion-free nilpotent.
Proposition 1.5 (Baumslag [Reference Baumslag4, Proposition 2.1(i)])
Suppose G is a group which is the union of an ascending chain of subgroups as follows:
$$ \begin{align*} G_0<G_1<G_2<\cdots<G_n<\cdots<G=\bigcup_{n=1}^{\infty}G_n. \end{align*} $$
Suppose each
$G_n$
is para-free of the same rank. If for each nonnegative integer n,
$|G_{n+1}:G_n[G_{n+1},G_{n+1}]|$
is finite, then G is residually torsion-free nilpotent.
Thus, Theorem 1.1 follows from the following lemma.
Lemma 1.6 Suppose L is an oriented two-bridge link, and let Y be the Alexander subgroup of L. If the Alexander polynomial of L has relatively prime coefficients, then Y can be written as a union of an ascending chain of subgroups
$Y_0<Y_1<Y_2<\cdots <Y$
such that:
-
(a) each
$Y_n$
is para-free of the same rank and -
(b)
$|Y_{n+1}:Y_n[Y_{n+1},Y_{n+1}]|$
is finite for each n.
Let H be a para-free group of rank r. An element
$h\in G$
is homologically primitive if the class of h in
$H/[H,H]\cong \mathbb{Z}^r$
can be extended to a basis.
Proposition 1.7 (Baumslag [Reference Baumslag3, Proposition 3])
Let H be a para-free group of rank r, and let
$\langle x \rangle $
be an infinite cyclic group generated by x. Let h be an element in H, and let n be a positive prime integer. If h generates its own centralizer and h is homologically primitive in H, then the group
$$\begin{align*}H\underset{h=x^n}{*}\langle x \rangle \end{align*}$$
is para-free of rank r.
Proposition 1.7 can be strengthened to the following statement.
Proposition 1.8 Let H be a para-free group of rank r, and let
$\langle x \rangle $
be an infinite cyclic group generated by x. Let h be an element in H, and let n be any positive integer. If h is homologically primitive in H, then
$$\begin{align*}H\underset{h=x^n}{*}\langle x \rangle \end{align*}$$
is para-free of rank r.
Proof Let H be a para-free group of rank r, and let h be an element in H which is homologically primitive. Suppose an element
$g\in H$
commutes with h, and consider,
$\langle g,h\rangle $
, the subgroup of H generated by g and h. A theorem of Baumslag [Reference Baumslag4, Theorem 4.2] states that any two-generator subgroup of a para-free group is free. Since g and h commute,
$\langle g,h\rangle $
cannot be a rank-2 free group, so
$\langle g,h\rangle $
is an infinite cyclic group. Since h is homologically primitive, it must be a generator of
$\langle g,h\rangle $
, so
$g=h^l$
for some integer l. Therefore, h generates its own centralizer.
Let
$n=p_1\cdots p_k$
be the prime decomposition of n. Let
$\langle x_1 \rangle ,\ldots ,\langle x_k\rangle $
be infinite cyclic groups. Define
$G_0=H$
and
$x_0=h$
. Then, for
$j=1,\ldots ,k$
, define
$$\begin{align*}G_j:=\frac{H*\langle x_1 \rangle*\cdots*\langle x_j\rangle}{N(x_0^{-1}x_1^{p_1},x_1^{-1}x_2^{p_2},\ldots,x_{j-1}^{-1}x_j^{p_j})}, \end{align*}$$
where N means the normal closure of the indicated elements. Thus,
$$ \begin{align} G_j=G_{j-1}\underset{x_{j-1}=x_j^{p_j}}{*}\langle x_j \rangle \end{align} $$
for each j. We can substitute
$x_{i}^{p_i}$
for
$x_{i-1}$
for
$i=1,\ldots , j$
so that
$$\begin{align*}G_j\cong H\underset{h=x_j^{n_j}}{*}\langle x_j \rangle, \end{align*}$$
where
$n_j=p_1\cdots p_j$
.
Since h is homologically primitive in H, the class of h in
$H'$
, the abelianization of H, extends to a basis
$\mathcal{B}$
of
$H'\cong \mathbb{Z}^r$
. After adjoining a root of h to obtain
$G_j$
,
$H'$
embeds into
$G^{\prime }_j$
, the abelianization of
$G_j$
.
The elements in
$\mathcal{B}$
remain linearly independent in
$G^{\prime }_k$
. Removing the class of h from
$\mathcal{B}$
and replacing it with the class of
$x_j$
produces a basis of
$G^{\prime }_j$
. Therefore,
$x_j$
is homologically primitive in
$G_j$
.
Since
$G_0=H$
is para-free of rank r, inductively, each
$G_j$
is para-free of rank r by (1.2) and Proposition 1.7. Thus,
$$\begin{align*}G_k\cong H\underset{h=x^n}{*}\langle x \rangle \end{align*}$$
is para-free of rank r.
Mayland [Reference Mayland and Newman19] proposes a strategy that uses the Reidemeister–Schreier rewriting process to describe the commutator subgroup of a two-bridge knot group as the union of an ascending chain of subgroups satisfying the conditions of Lemma 1.6. The first term
$Y_0$
is a free group, and ideally, for each
$n\geq 1$
,
$Y_n$
is isomorphic to
$Y_{n-1}$
after adjoining roots of homologically primitive elements, in the manner of Proposition 1.8, a finite number of times. Mayland attempts to show that, for a given two-bridge knot, each
$Y_n$
is obtained by adjoining roots to
$Y_{n-1}$
using a recursive argument. However, it is not at all obvious that Mayland’s recursive argument is valid. While it is straightforward to verify Mayland’s argument on a case-by-case basis, proving his recursive argument works in general is quite difficult. Furthermore, there are errors in Mayland’s argument that the elements, whose roots are adjoined, are homologically primitive. Unfortunately, Mayland never published a proof of his assertion. In a later paper by Mayland and Murasugi [Reference Mayland and Murasugi20], it is stated that Mayland plans to present a proof using a different strategy. This paper has not appeared.
Here, we use a slightly different approach. In this paper, we use a graph-theoretic construction similar to one used by Hirasawa and Murasugi [Reference Hirasawa and Murasugi11] to relate the Alexander subgroups of more complicated two-bridge link groups to those of simpler two-bridge link groups. Then, it is proved inductively that the Alexander subgroups of all two-bridge links can be described by adjoining roots to a free group, and we show that when two-bridge links have Alexander polynomials with relatively prime coefficients, their Alexander subgroups satisfy Lemma 1.6 via Mayland’s strategy.
1.2 Application to bi-orderability
Residually torsion-free nilpotence is useful for determining when a link group is bi-orderable, i.e., admits a total order invariant under both left and right multiplication [Reference Clay, Desmarais and Naylor7, Reference Perron and Rolfsen25, Reference Yamada30]. Let L be a smooth link in
$S^3$
. The link group
$\pi (L)$
is an extension of
$\langle t\rangle $
(an infinite cyclic group generated by t) by the Alexander subgroup Y. Let
$Y^{\textsf{ab}}$
denote the abelianization of Y, and let
$L_t$
be the linear map induced on
$\mathbb{Q}\otimes Y^{\textsf{ab}}$
by conjugating Y by t. The following result is shown by Linnell, Rhemtulla, and Rolfsen [Reference Linnell, Rhemtulla and Rolfsen13] and is stated more explicitly by Chiswell, Glass, and Wilson [Reference Chiswell, Glass and Wilson6].
Theorem 1.9 (Chiswell–Glass–Wilson [Reference Chiswell, Glass and Wilson6, Theorem B])
Suppose Y is residually torsion-free nilpotent. If the dimension of
$\mathbb{Q}\otimes Y^{\textsf{ab}}$
is finite and all the eigenvalues of
$L_t$
are real and positive, then
$\pi (L)$
is bi-orderable.
The Alexander polynomial of L,
$\Delta _L(t)$
, is a scalar multiple of the characteristic polynomial of
$L_t$
, and the dimension of
$\mathbb{Q}\otimes Y^{\textsf{ab}}$
is the degree of
$\Delta _L(t)$
(for details, see [Reference Rolfsen27, Chapter VIII]), which implies the following corollary.
Corollary 1.10 Let L be a link in
$S^3$
. If the Alexander subgroup of L is residually torsion-free nilpotent and
$\Delta _L(t)$
has all real positive roots, then
$\pi (L)$
is bi-orderable.
Remark 1.11 Linnell, Rhemtulla, and Rolfsen actually show that a weaker condition on the Alexander polynomial is sufficient for bi-orderability. However, since two bridge links are alternating, the coefficients of their Alexander polynomials alternate sign [Reference Crowell8], so the signs of the even degree terms are all opposite to the signs of the odd degree terms. It follows that the Alexander polynomials of two-bridge links cannot have negative roots. Therefore, for a two-bridge link, having an Alexander polynomial which is “special” in the sense of Linnell, Rhemtulla, and Rolfsen [Reference Linnell, Rhemtulla and Rolfsen13] is equivalent to the Alexander polynomial having all real and positive roots.
By combining Theorem 1.1 with Corollary 1.10, we have the following result.
Theorem 1.12 Let L be an oriented two-bridge link with Alexander polynomial
$\Delta _L(t)$
. If all the roots of
$\Delta _L(t)$
are real and positive and the coefficients of
$\Delta _L(t)$
are relatively prime, then the link group of L is bi-orderable. In particular, if K is a two-bridge knot and all the roots of
$\Delta _K(t)$
are real and positive, then the knot group of K is bi-orderable.
Remark 1.13 Theorem 1.12 is not true if either condition on the Alexander polynomial is removed. The link group of the
$(4,2)$
-torus link has presentation
$$\begin{align*}\langle x,y| x^{-1}y^{-2}xy^2\rangle. \end{align*}$$
Since x and y do not commute but x commutes with
$y^2$
, the
$(4,2)$
-torus link does not have bi-orderable link group [Reference Neumann24, Lemma 1.1]. As stated in Remark 1.2, the
$(4,2)$
-torus link, oriented as in Figure 1, has Alexander polynomial
$2t-2$
, which has only one real positive root but does not have relatively prime coefficients. If we reverse the orientation of one of the components, the Alexander polynomial is
$t^3-t^2+t-1$
, which has relatively prime coefficients, but no real roots.
1.3 A family of bi-orderable two-bridge links
Every oriented two-bridge link is the closure of rational tangle. Thus, by Conway’s correspondence, we can associate a two-bridge link to a rational fraction
$p/q$
with
$p>0$
(see [Reference Burde and Zieschang5, Chapter 12] for details). Let
$L(p/q)$
denote the two-bridge link represented by
$p/q$
. Choose an orientation of
$L(p/q)$
so that the two overstrands of Schubert’s projection of
$L(p/q)$
are oriented away from each other, as shown in Figure 2. This correspondence satisfies the following properties:
Figure 2: Schubert’s projection of
$L(8/3)$
.
-
(1)
$L(p/q)$
and
$L(p'/q')$
are equivalent as unoriented links if and only if:-
(a)
$p=p'$
and -
(b)
$q\cong q'\;(\textsf{mod}\, p)$
or
$qq'\cong 1\;(\textsf{mod}\, p)$
.
-
-
(2)
$L(p/q)$
and
$L(p'/q')$
are equivalent as oriented links if and only if:-
(a)
$p=p'$
and -
(b)
$q\cong q'\;(\textsf{mod}\, 2p)$
or
$qq'\cong 1\;(\textsf{mod}\, 2p)$
.
-
-
(3)
$L(p/q)$
is a knot if and only if p is odd. -
(4)
$L(p/q)$
and
$L(-p/q)$
are mirrors. -
(5) If
$L(p/q)$
is a link,
$L(p/(q\pm p))$
is the oriented link obtained by reversing the orientation of one of the components of
$L(p/q)$
.
When q is odd, there are nonzero integers
$k_1,\ldots ,k_n$
such that
$p/(p-q)=[2k_1,\ldots ,2k_n]$
. Here,
$[2k_1,\ldots ,2k_n]$
denotes the continued fraction expansion
$$\begin{align*}[2k_1,\ldots,2k_n]=2k_1+\frac{1}{2k_2+\frac{1}{2k_3+\frac{1}{\cdots+\frac{1}{2k_n}}}}. \end{align*}$$
The integers
$2k_1,\ldots ,2k_n$
correspond to the number of twist in the rational tangle
$p/q$
(see Figure 3). See [Reference Murasugi23, Chapter 9] for details on fraction expansions and rational tangles. When n is even,
$L(p/q)$
is a knot with genus
$n/2$
. When n is odd,
$L(p/q)$
is a two-component link with genus
$(n-1)/2$
.
Figure 3: Rational tangle form of a two-bridge knot (top) and link (bottom).
Every oriented two-bridge link is associated to a fraction
$p/q$
with q odd and
$|p/q|>1$
. When
$L(p/q)$
is a link, p is always even and q is always odd. Suppose
$L(p/q)$
is a knot with q even. Let
$q'$
be the inverse q modulo
$2p$
. Since q is even,
$q'$
is odd, and
$L(p/q)$
is equivalent to
$L(p/q')$
. Furthermore, since
$L(p/q)$
is equivalent to
$L(p/(q+2pk))$
for all integers k, q can be chosen such that
$-p<q<p$
so
$|p/q|>1$
. Therefore, we adopt the convention that
$p>|q|>0$
and q is odd.
Chiswell, Glass, and Wilson showed that groups that admit presentations with two generators and one relator satisfying certain conditions have residually torsion-free nilpotent commutator subgroups [Reference Chiswell, Glass and Wilson6]. Clay, Desmarais, and Naylor used this to show that twist knots (knots represented by
$[2,2k]$
with
$k>0$
) have bi-orderable knot groups in [Reference Clay, Desmarais and Naylor7]. In [Reference Yamada30], Yamada used the same idea to extend this to the family of two-bridge links represented by
$[2,2,\ldots ,2,2k]$
, where
$k>0$
. Using the following result of Lyubich and Murasugi, this paper extends this family further.
Theorem 1.14 (Lyubich–Murasugi [Reference Lyubich and Murasugi16, Theorem 2])
Let
$p/q$
be a fraction of co-prime integers p and q with
$q\neq 0$
, and let L be the two-bridge link
$L(p/q)$
. If for some positive integer n,
$p/q=[2k_1,\ldots ,2k_n]$
with
$k_i>0$
for each
$i=1,\ldots ,n$
, then all the roots of
$\Delta _L(t)$
are real and positive.
Combining this theorem with Corollary 1.3 implies the following.
Corollary 1.15 Let
$p/q$
be a fraction of co-prime integers p and q with
$q\neq 0$
, and
$p/(p-q)=[2k_1,\ldots ,2k_n]$
with
$k_i>0$
for each
$i=1,\ldots ,n$
.
If the coefficients of the Alexander polynomial of
$L(p/q)$
are relatively prime, then the link group of
$L(p/q)$
is bi-orderable. In particular, when
$L(p/q)$
is a knot, the knot group of
$L(p/q)$
is bi-orderable.
Theorem 1.14 does not characterize all two-bridge links with Alexander polynomial that have all real and positive roots.
Example 1.16 Let
$K=L(81/49)$
.
$81/(81-49)=[2,2,-8,-2]$
,
$$\begin{align*}\Delta_K(t)=4t^4-20t^3+33t^2-20t+4=(t-2)^2(2t-1)^2, \end{align*}$$
which has two real roots of multiplicity 2. Thus, the knot group of K is bi-orderable.
1.4 Genus one two-bridge links
Suppose L is an oriented genus-one two-bridge link
$L(p/q)$
. When L is a genus-one knot,
$p/(p-q)=[2k_1,2k_2]$
for some nonzero integers
$k_1$
and
$k_2$
. The Alexander polynomial of L is
$$\begin{align*}\Delta_{L}(t)=k_1k_2t^2-(2k_1k_2+1)t+k_1k_2. \end{align*}$$
When
$k_1k_2>0$
,
$\Delta _L(t)$
has two positive real roots, so
$\pi (L)$
is bi-orderable by Theorem 1.12. When
$k_1k_2<0$
,
$\Delta _L(t)$
has no real roots. In this case, since
$\deg \Delta _L=2$
, an obstruction by Clay, Desmarais, and Naylor [Reference Clay, Desmarais and Naylor7, Theorem 3.3] implies that
$\pi (L)$
is not bi-orderable.
Proposition 1.17 Suppose L is the two-bridge knot
$L(p/q)$
with
$p/(p-q)=[2k_1,2k_2]$
. The knot group
$\pi (L)$
is bi-orderable if and only if
$k_1k_2>0$
.
When L is a genus-one two-component link,
$p/(p-q)=[2k_1,2k_2,2k_3]$
for some nonzero integers
$k_1$
,
$k_2$
, and
$k_3$
. The Alexander polynomial of
$L(p/q)$
is
$$ \begin{align*} \Delta_L(t)&=k_1k_2k_3t^3-(3k_1k_2k_3+k_1+k_3)t^2+(3k_1k_2k_3+k_1+k_3)t-k_1k_2k_3\\ &=(t-1)(k_1k_2k_3t^2-(2k_1k_2k_3+k_1+k_3)t+k_1k_2k_3). \end{align*} $$
The discriminant, D, of the second factor is
$$\begin{align*}D=4k_1k_2k_3(k_1+k_3)+(k_1+k_3)^2, \end{align*}$$
so
$D\geq 0$
if
$k_1k_2k_3(k_1+k_3)\geq 0$
. It follows that
$\Delta _L(t)$
has three real positive roots when
$k_1k_2k_3(k_1+k_3)\geq 0$
.
Let
$A=k_1k_2k_3$
and
$B=3k_1k_2k_3+k_1+k_3$
. The coefficients of
$\Delta _L$
are relatively prime precisely when
$\gcd (A,B)=1$
, and
$\gcd (A,B)=1$
if and only if
$\gcd (k_1,k_3)=1$
and
$\gcd (k_2,k_1+k_3)=1$
.
Therefore, Theorem 1.12 implies the following result.
Proposition 1.18 Suppose L is the two-component two-bridge link
$L(p/q)$
with
$p/(p-q)=[2k_1,2k_2,2k_3]$
. If
$\gcd (k_1,k_3)=1$
,
$\gcd (k_2,k_1+k_3)=1$
, and
$k_1k_2k_3(k_1+k_3)\geq 0$
, then
$\pi (L)$
is bi-orderable.
1.5 Application to ribbon concordance
The residual torsion-free nilpotence of the commutator subgroup of a knot group has an application to ribbon concordance as well. Given two knots
$K_0$
and
$K_1$
in
$S^3$
, A ribbon concordance from
$K_1$
to
$K_0$
is a smoothly embedded annulus C in
$[0,1]\times S^3$
such that C has boundary
$-(\{0\}\times K_0) \cup \{1\}\times K_1$
and C has only index 0 and 1 critical points.
$K_1$
is said to be ribbon concordant to
$K_0$
, denoted
$K_1\geq K_0$
, if there is a ribbon concordance from
$K_1$
to
$K_0$
. The relation
$\geq $
is clearly reflexive and transitive. Gordon [Reference Gordon10] conjectures that
$\geq $
is a partial order on knots in
$S^3$
.
Gordon gives conditions under which
$\geq $
behaves antisymmetrically.
Theorem 1.19 (Gordon [Reference Gordon10])
If
$K_0\geq K_1$
and
$K_1\geq K_0$
and the commutator subgroup of
$\pi (K_0)$
is transfinitely nilpotent, then
$K_0$
and
$K_1$
are ambient isotopic.
Remark 1.20 Transfinite nilpotence follows from residual torsion-free nilpotence (see [Reference Gordon10] for a definition of transfinitely nilpotent).
Here, we state the following corollary.
Corollary 1.21 If
$K_1\geq K_0$
and
$K_0\geq K_1$
and
$K_0$
is a two-bridge knot, then
$K_0$
and
$K_1$
are ambient isotopic.
Remark 1.22 Since this article’s initial posting, Agol showed that Gordon’s conjecture is true [Reference Agol1] subsuming Corollary 1.21.
1.6 Outline
The rest of this paper is devoted to the proof of Lemma 1.6. In Section 2, we illustrate the proof of Lemma 1.6 by verifying the lemma for the two-bridge knot
$L(17/13)$
. Section 3 investigates the properties of a presentation for the Alexander subgroup Y obtained by the Reidemeister–Schreier rewriting procedure. The proof of Lemma 1.6 is completed in Section 3.4. In Section 4, we define the cycle graph of a two-bridge link. Cycle graphs are used to prove a key lemma in Section 5.
The Appendix covers some background material on presentation matrices of modules over a principal ideal domain (PID).
2 An example
In this section, we use the two-bridge knot
$K:=L(17/13)$
to provide an example of the proof of Lemma 1.6. Using the Schubert normal form [Reference Schubert29], we obtain a presentation of
$\pi (K)$
:
$$\begin{align*}\pi(K)=\langle a,b\; | \; avb^{-1}v^{-1} \rangle, \end{align*}$$
where
$$\begin{align*}v = ba^{-1} ba^{-1} b^{-1}a b^{-1}a ba^{-1} ba^{-1} b^{-1}a b^{-1}a. \end{align*}$$
Denote the Alexander subgroup of
$\pi (K)$
by Y. Using the Reidemeister–Schreier rewriting process, we obtain the following presentation of Y (see Section 3 for details):
$$\begin{align*}Y\cong\langle \{S_k\}_{k\in\mathbb{Z}}\; | \;\{R_k\}_{k\in\mathbb{Z}}\rangle. \end{align*}$$
Here,
$S_k:=a^kba^{-k-1}$
and the relators
$R_k$
are defined as follows:
$$\begin{align*}\vdots \end{align*}$$
$$ \begin{align*} R_{-1}&:= S_0 S_0 S_{-1}^{-1} S_{-1}^{-1} S_0 S_0 S_{-1}^{-1} S_{-1}^{-1} S_{-1}^{-1} S_{-2} S_{-2} S_{-1}^{-1} S_{-1}^{-1} S_{-2} S_{-2} S_{-1}^{-1} S_{-1}^{-1}, \\ R_0 &:= S_1 S_1 S_0^{-1} S_0^{-1} S_1 S_1 S_0^{-1} S_0^{-1} S_0^{-1} S_{-1} S_{-1} S_0^{-1} S_0^{-1} S_{-1} S_{-1} S_0^{-1} S_0^{-1}, \\ R_1 &:= S_2 S_2 S_1^{-1} S_1^{-1} S_2 S_2 S_1^{-1} S_1^{-1} S_1^{-1} S_0 S_0 S_1^{-1} S_1^{-1} S_0 S_0 S_1^{-1} S_1^{-1}, \end{align*} $$
$$\begin{align*}\vdots \end{align*}$$
Define a sequence of groups
$\{Y_n\}_{n=0}^{\infty }$
as follows:
$$ \begin{align*} Y_0 &:=\langle S_{-1}, S_0\,|\,\emptyset\rangle,\\ Y_1 &:=\langle S_{-2}, S_{-1}, S_0, S_1\; | \; R_{-1}, R_0\rangle,\\ Y_2 &:=\langle S_{-3}, S_{-2}, S_{-1}, S_0, S_1, S_2\; | \; R_{-2}, R_{-1}, R_0, R_1\rangle, \end{align*} $$
$$\begin{align*}\vdots \end{align*}$$
Define
$\widehat {A}_1$
,
$\widehat {A}_2$
,
$\widehat {V}_1$
, and
$\widehat {V}_2$
as follows:
$$ \begin{align} \begin{aligned} \widehat{A}_1&=S_1^2S_0^{-2},\\ \widehat{A}_2&=S_1,\\ \widehat{V}_1&=S_0^{-1} S_{-1}^2 S_0^{-2} S_{-1}^2 S_0^{-2},\\ \widehat{V}_2&=S_0^{-2}. \end{aligned} \end{align} $$
Let
$H_1$
be the group obtained by adjoining a square root of
$\widehat {V}_1^{-1}$
to
$Y_0$
as follows:
$$\begin{align*}H_1:=Y_0\underset{\widehat{V}_1^{-1}=t_1^2}{*}\langle t_1 \rangle. \end{align*}$$
Similarly, let
$H_2$
be the group obtained by adjoining a square root of
$t_1\widehat {V}_2^{-1}$
to
$H_1$
as follows:
$$\begin{align*}H_2:=H_1\underset{t_1\widehat{V}_2^{-1}=S_1^2}{*}\langle S_1 \rangle. \end{align*}$$
Thus,
$H_2$
has the following group presentation:
$$ \begin{align*} H_2 &\cong \langle S_{-1}, S_0, S_1, t_1\; | \; t_1^2\widehat{V}_1=1,t_1=S_1^2\widehat{V}_2\rangle \\ &\cong \langle S_{-1}, S_0, S_1\; | \; (S_1^2\widehat{V}_2)^2\widehat{V}_1=1,\rangle \\ &\cong \langle S_{-1}, S_0, S_1\; | \; R_0\rangle. \end{align*} $$
Define
,
,
, and
as follows:
Let
$H_3$
be the group obtained by adjoining a square root of
to
$H_2$
:
Let
$H_4$
be the group obtained by adjoining a square root of
to
$H_3$
:
Therefore,
$H_4$
is isomorphic to
$Y_1$
:
In conclusion,
$Y_1$
is
$Y_0$
after adjoining roots four times, and since
$R_{n\pm 1}$
is
$R_{n}$
with all the subscripts changed by
$\pm 1$
,
$Y_{n+1}$
is
$Y_n$
after adjoining roots four times. Thus, for each n,
$Y_n$
embeds into
$Y_{n+1}$
. Therefore, Y is the union of an ascending chain of subgroups as follows:
$$\begin{align*}Y_0< Y_1<\cdots< Y=\bigcup_{n=0}^{\infty}Y_n. \end{align*}$$
By Proposition 1.5, if each
$Y_n$
is para-free of the same rank, then Y is residually torsion-free nilpotent.
$Y_0$
is clearly para-free of rank 2 since it is a rank-2 free group. We need to verify that each time we adjoin a root of an element, that element is homologically primitive. Then, by Proposition 1.8, we can conclude that each
$Y_n$
is also para-free of rank 2.
Claim For each
$n\geq 0$
, if
$Y_n$
is para-free of rank 2, then so is
$Y_{n+1}$
.
Proof Let n be a nonnegative integer, and suppose
$Y_n$
is para-free of rank 2. In an abuse of notation, let
$\widehat {A}_1$
,
$\widehat {A}_2$
,
$\widehat {V}_1$
, and
$\widehat {V}_2$
be as defined in (2.1) except with the subscripts of each
$S_i$
increased by n. Similarly, let
,
,
, and
be as defined in (2.2) except with the subscripts of each
$S_i$
decreased by n. Also, let
$H_1$
,
$H_2$
,
$H_3$
, and
$H_4$
be the groups obtained by adjoining square roots of
$\widehat {V}_1^{-1}$
,
$t_1\widehat {V}_2^{-1}$
,
, and
to
$Y_n$
as before.
Let
$Y_n^{\textsf{ab}}$
denote the abelianization of
$Y_n$
, and let
$B_1$
be the quotient of
$Y_n^{\textsf{ab}}$
obtained by killing the class of
$\widehat {V}_1^{-1}$
in
$Y_n^{\textsf{ab}}$
. Since
$Y_n$
is para-free of rank 2,
$Y_n^{\textsf{ab}}\cong \mathbb{Z}\oplus \mathbb{Z}$
. Thus,
$$\begin{align*}B_1\cong\mathbb{Z}\oplus\frac{\mathbb{Z}}{C\mathbb{Z}} \end{align*}$$
for some integer C.
Now, we view
$Y_n^{\textsf{ab}}$
as a
$\mathbb{Z}$
-module and use addition as the group operation.
$Y_n^{\textsf{ab}}$
is generated by
$S^{\prime }_{-n-1},S_{-n}',\dots ,S_n'$
, where
$S^{\prime }_i$
denotes the class of
$S_i$
in
$Y_n^{\textsf{ab}}$
. Using this generating set,
$Y_n^{\textsf{ab}}$
has a
$(2n)\times (2n+2)$
presentation matrix:
$$\begin{align*}\left( \begin{array}{cccccc} 4 & -9 & 4 & & & \\ & 4 & -9 & 4 & & \\ & & \ddots & \ddots & \ddots & \\ & & & 4 & -9 & 4 \end{array} \right). \end{align*}$$
Throughout this paper, missing entries in matrices are zeros. See the Appendix for definition and background on presentation matrices. The class of
$\widehat {V}_1^{-1}$
in
$Y_n^{\textsf{ab}}$
is
$-4S_{n-1}'+5S_n'$
. Thus,
$B_1$
has the following
$(2n+1)\times (2n+2)$
presentation matrix, which we will also call
$B_1$
:
$$\begin{align*}B_1=\left( \begin{array}{cccccc} 4 & -9 & 4 & & & \\ & 4 & -9 & 4 & & \\ & & \ddots & \ddots & \ddots & \\ & & & 4 & -9 & 4\\ & & & & -4 & 5 \end{array} \right). \end{align*}$$
By Lemma A.1, the integer C is the greatest common divisor of the determinants of every
$(2n+1)\times (2n+1)$
minor of
$B_1$
. By deleting the last column, we get a square minor of
$B_1$
with determinant
$-4^{2n+1}$
. However, by deleting the first column, we see
$B_1$
has a minor with odd determinant. (Modulo 2, the matrix obtained from
$B_1$
by deleting the first column is the identity matrix.) Thus,
$C=1$
.
Therefore,
$B_1$
is a rank-1 free abelian group. It follows that
$\widehat {V}_1^{-1}$
is homologically primitive in
$Y_n$
, and
$H_1$
is para-free of rank 2 by Proposition 1.8.
Let
$B_2$
be the quotient of
$H_1^{\textsf{ab}}$
obtained by killing the class of
$t_1\widehat {V}_2^{-1}$
in
$H_1^{\textsf{ab}}$
, the abelianization of
$H_1$
.
$H_1^{\textsf{ab}}$
is generated by
$S^{\prime }_{-n-1},S_{-n}',\dots ,S_n',t^{\prime }_1$
, where
$t^{\prime }_1$
is the class of
$t_1$
in
$H_1^{\textsf{ab}}$
.
$H_1^{\textsf{ab}}$
has a
$(2n+1)\times (2n+3)$
presentation matrix:
$$\begin{align*}\left( \begin{array}{ccccccc} 4 & -9 & 4 & & & & \\ & 4 & -9 & 4 & & & \\ & & \ddots & \ddots & \ddots & & \\ & & & 4 & -9 & 4 & \\ & & & & -4 & 5 & 2 \end{array} \right). \end{align*}$$
The class of
$t_1\widehat {V}_2^{-1}$
in
$H_1^{\textsf{ab}}$
is
$2S_n'+t^{\prime }_1$
. Thus,
$B_2$
has the following
$(2n+2)\times (2n+3)$
presentation matrix:
$$\begin{align*}B_2=\left( \begin{array}{ccccccc} 4 & -9 & 4 & & & & \\ & 4 & -9 & 4 & & & \\ & & \ddots & \ddots & \ddots & & \\ & & & 4 & -9 & 4 & \\ & & & & 4 & -5 & 2\\ & & & & & 2 & 1 \end{array} \right). \end{align*}$$
Using the 1 in the bottom-right corner, we apply a row and a column operation. Then, we kill the last row and column to get the following presentation matrix:
$$\begin{align*}B_2\cong\left( \begin{array}{cccccc} 4 & -9 & 4 & & & \\ & 4 & -9 & 4 & & \\ & & \ddots & \ddots & \ddots & \\ & & & 4 & -9 & 4\\ & & & & 4 & -9 \\ \end{array} \right). \end{align*}$$
Thus,
$B_2$
is a rank-1 free abelian group, by an argument similar to the one used for
$B_1$
. It follows that
$t_1\widehat {V}_2^{-1}$
is homologically primitive in
$H_1$
, and
$H_2$
is para-free of rank 2 by Proposition 1.8.
Similarly,
and
are homologically primitive in
$H_2$
and
$H_3$
, respectively. Therefore,
$H_4\cong Y_{n+1}$
is para-free of rank 2.
For any group G, if H is G with an nth root adjoined, then
$$\begin{align*}H/G\cong \mathbb{Z}/n\mathbb{Z}\, , \end{align*}$$
so
$|H:G[H,H]|=|H:G|=n$
. Thus, since for each n,
$Y_{n+1}$
is
$Y_n$
with square roots adjoined four times,
$|Y_{n+1}:Y_n[Y_{n+1},Y_{n+1}]|=16$
.
Since
$Y_0$
is para-free of rank 2, each
$Y_n$
is para-free of rank 2 by induction. Therefore, Y is residually torsion-free nilpotent by Proposition 1.5.
3 A group presentation of the Alexander subgroup
In this section, we give a group presentation of the Alexander subgroup of an arbitrary two-bridge link group using the Reidemeister–Schreier rewriting process. From this presentation of the Alexander subgroup, we can describe the subgroup as the union of an ascending chain of subgroups which satisfy conditions (a) and (b) of Lemma 1.6 when the Alexander polynomial of the link has relatively prime coefficients.
3.1 A presentation from Reidemeister–Schreier
Consider the two-bridge link
$L:=L(p/q)$
where
$1\leq |q|<p$
with q odd. For each integer i, define
$$ \begin{align} \epsilon_i:=(-1)^{\lfloor \frac{iq}{p}\rfloor}. \end{align} $$
Proposition 3.1 (Schubert [Reference Schubert29])
Given the two-bridge link
$L(p/q)$
,
$$\begin{align*}\pi(L(p/q))\cong\langle a,b | w\rangle, \end{align*}$$
where a and b are classes of meridians of
$L(p/q)$
and
$w=a^{\epsilon _0}b^{\epsilon _1}\ldots a^{\epsilon _{2p-2}}b^{\epsilon _{2p-1}}$
.
Let Y be the Alexander subgroup of L. A group presentation for Y can be obtained using the Reidemeister–Schreier rewriting procedure, developed by Reidemeister [Reference Reidemeister26] and Schreier [Reference Schreier28]. The Reidemeister–Schreier rewriting procedure is described in detail in Section 2.3 of the text by Karrass, Magnus, and Solitar [Reference Karrass, Magnus and Solitar12]. The application of this procedure to the situation at hand is discussed below.
Under the map
$\varphi \circ h:\pi (L)\to \pi (L)/Y\cong \mathbb{Z}$
from (1.1), a and b are both sent to 1 or both sent to
$-1$
. Consider
$\mathcal{A}:=\{a^k\}_{k\in \mathbb{Z}}$
as a set of coset representatives for
$\pi (L)/Y$
. Given an element x in
$\pi (L)$
, let
$\overline {x}$
be the coset representative of x in
$\mathcal{A}$
. For each
$x\in \{a,b\}$
and
$k\in \mathbb{Z}$
, define
$$\begin{align*}\gamma(a^k,x):=a^kx(\overline{a^kx})^{-1}. \end{align*}$$
Note that
$\gamma (a^k,a)=1$
and
$\gamma (a^k,b)=a^kba^{-k-1}$
. Given a word
$u=x_1^{s_1}x_2^{s_2}\cdots x_n^{s_n}$
with
$x_i\in \{a,b\}$
and
$s_i\in \{1,-1\}$
for all i, define
$$\begin{align*}\tau(u):=\gamma(\overline{t_1},x_1)^{s_1}\gamma(\overline{t_2},x_2)^{s_2}\cdots\gamma(\overline{t_n},x_n)^{s_n}, \end{align*}$$
where
$$\begin{align*}t_i:= \left\{\begin{array}{ll} x_1^{s_1}\cdots x_{i-1}^{s_{i-1}}\text{ (possibly trivial)}\,,&s_i=1,\\ x_1^{s_1}\cdots x_i^{s_i},&s_i=-1.\\ \end{array} \right. \end{align*}$$
For each integer k, define
$$\begin{align*}S_k:=\gamma(a^k,b) \end{align*}$$
and define
$$\begin{align*}\mathcal{S}:=\{S_k\}_{k\in\mathbb{Z}}\,. \end{align*}$$
Since, for all k,
$\gamma (a^k,a)=1$
, for each word u,
$\tau (u)$
is a product
$S_{k_1}S_{k_2}\cdots S_{k_l}$
. For each integer k, define
$$\begin{align*}R_k:=\tau(a^kwa^{-k}). \end{align*}$$
Define
$$ \begin{align} \sigma_i:=\left\{ \begin{array}{ll} \sum_{j=0}^{i-1}\epsilon_j, & \text{when }i> 0,\\ \sum_{j=i}^{-1}\epsilon_j, & \text{when }i< 0,\\ 0,&\text{when }i=0, \end{array} \right. \end{align} $$
for each integer i.
Proposition 3.2 Suppose
$R_0=\tau (w)=S_{i_1}^{\eta _1}S_{i_2}^{\eta _2}\ldots S_{i_{n}}^{\eta _{n}}$
, where each
$i_j$
is an integer and each
$\eta _j$
is
$\pm 1$
. Then:
-
(a)
$n=p$
. -
(b)
$\eta _j=\epsilon _{2j-1}$
, for each
$j=1,\ldots ,p$
. -
(c)
$i_j=\sigma _{2j}$
if
$\eta _j=1$
and
$i_j=\sigma _{2j+1}$
if
$\eta _j=-1$
for each
$j=1,\ldots ,p$
. -
(d) For every integer k,
$R_k=S_{i_1+k}^{\eta _1}S_{i_2+k}^{\eta _2}\ldots S_{i_{p}+k}^{\eta _{p}}$
.
Proof Since
$\gamma (a^k,a)$
is trivial, the
$S_i$
-generators in
$R_0$
come from the b-generators in w. For (a), notice that the length of the word
$R_0$
is the number of times b and
$b^{-1}$
appear in w, which is equal to p. By definition,
$\eta _j$
is equal to the exponent of the corresponding b or
$b^{-1}$
in w, which is
$\epsilon _{2j-1}$
showing (b). Since
$a=b$
modulo Y, then for any word u in a and b,
$\overline {u}=a^s$
where s is the sum of the exponents of the a’s and b’s in u. Thus, both (c) and (d) follow by a straightforward computation.
Proposition 3.3 (Karrass–Magnus–Solitar [Reference Karrass, Magnus and Solitar12, Theorem 2.9])
$$\begin{align*}Y\cong\langle \{S_k\}_{k\in\mathbb{Z}}\; | \;\{R_k\}_{k\in\mathbb{Z}}\rangle. \end{align*}$$
3.2 Group presentation properties
This group presentation of Y has a few notable properties which will be of use.
Given a word W in
$\mathcal{S}$
, let
$[W]$
denote the class of W in the free abelian group generated by
$\mathcal{S}$
. For each integer k, define
$S^{\prime }_k:=[S_k]$
. Denote the maximal and minimal subscripts of S appearing in the word
$R_0$
by M and m, respectively, so that
$$\begin{align*}[R_0]=a_MS^{\prime}_{M}+a_{M-1}S^{\prime}_{M-1}+\cdots+a_{m+1}S^{\prime}_{m+1}+a_mS^{\prime}_{m} \end{align*}$$
for some integers
$a_m,\ldots ,a_M$
.
Proposition 3.4 Suppose L is a two-bridge link, and suppose Y is the Alexander subgroup of L with presentation as defined in Section 3.1.
-
(a) For each integer n,
$$\begin{align*}[R_n]=a_MS^{\prime}_{M+n}+a_{M-1}S^{\prime}_{M-1+n}+\cdots+a_{m+1}S^{\prime}_{m+1+n}+a_nS^{\prime}_{m+n}. \end{align*}$$
-
(b) Let g be the genus of L. When L is a knot,
$M-m=2g$
, and when L is a link,
$M-m=2g+1$
. -
(c) For all
$j=m,\ldots ,M$
, where
$$\begin{align*}a_j=\left\{ \begin{array}{ll} \underline{a}_{g+m-j}, & \text{if } m\leq j \leq m+g, \\ \underline{a}_{g+j-M}, & \text{if } M-g\leq j \leq M, \end{array} \right. \end{align*}$$
when L is a knot, and
$$\begin{align*}\Delta_L(t)=\underline{a}_gt^{2g}+\cdots+\underline{a}_0t^g+\cdots+\underline{a}_g \end{align*}$$
when L is a link. In particular, for all
$$\begin{align*}\Delta_L(t)=\underline{a}_gt^{2g+1}+\cdots+\underline{a}_0t^{g+1}+\underline{a}_0t^{g}+\cdots+\underline{a}_g \end{align*}$$
$j=0,\ldots , M-m$
,
$$\begin{align*}a_{M-j}=a_{m+j}. \end{align*}$$
Proof Part (a) follows from Proposition 3.2 (d).
For each
$i=1,\ldots ,2p$
, denote by
$w_i$
the word obtained from the first i generators of the relation w. Also, define
$$\begin{align*}\theta(s):= \left\{\begin{array}{ll} 1, & \text{if }s=1,\\ 0, & \text{if }s=-1. \end{array} \right. \end{align*}$$
We compute the Alexander polynomial by performing Fox calculus on w with respect to b (see [Reference Fox9, Section 3]):
$$ \begin{align*} \frac{\partial w}{\partial b}&=a^{\epsilon_0}\left(\frac{\partial}{\partial b}(b^{\epsilon_1}) +b^{\epsilon_1}a^{\epsilon_2}\left(\frac{\partial}{\partial b}(b^{\epsilon_3})\right)+\cdots+ b^{\epsilon_{2p-3}}a^{\epsilon_{2p-2}}\left(\frac{\partial}{\partial b}(b^{\epsilon_{2p-1}}) \right)\cdots\right)\\ &=\sum_{i=1}^{p}w_{2i-1}\frac{\partial}{\partial b}(b^{\epsilon_{2i-1}})\\ &=\sum_{i=1}^{p}\epsilon_{2i-1} w_{f(i)}, \end{align*} $$
where
$$\begin{align*}f(i)=2i-\theta(\epsilon_{2i-1}). \end{align*}$$
For each
$i=1,\ldots ,2p$
,
$\overline {w_i}=a^{\sigma _i}$
. Let
$t=\overline {a}=\overline {b}$
. Up to multiplication by powers of t,
$$ \begin{align} \Delta_L(t)=\varphi'\left(\frac{\partial w}{\partial b}\right)=\sum_{i=1}^{p}\epsilon_{2i-1} t^{\sigma_{f(i)}}, \end{align} $$
where
$\varphi ':\mathbb{Z}[\pi (L)]\to \mathbb{Z}[t]$
is the map induced by
$\varphi \circ h$
.
By Proposition 3.2,
$$\begin{align*}R_k=S_{\sigma_{f(1)}+k}^{\epsilon_1}S_{\sigma_{f(2)}+k}^{\epsilon_3} \cdots S_{\sigma_{f(p)}+k}^{\epsilon_{2p-1}}, \end{align*}$$
so
$$ \begin{align} \begin{aligned} [R_k]&=\epsilon_1S^{\prime}_{\sigma_{f(1)}+k}+\epsilon_3S^{\prime}_{\sigma_{f(2)}+k}+ \cdots+\epsilon_{2p-1}S^{\prime}_{\sigma_{f(p)}+k}\\ &=\sum_{i=1}^{p}\epsilon_{2i-1}S^{\prime}_{\sigma_{f(i)}+k}. \end{aligned} \end{align} $$
The degree of
$\Delta _L$
is
$2g$
when L is a knot and
$2g+1$
when L is a link [Reference Crowell8, Reference Murasugi21, Reference Murasugi22]. Thus, parts (b) and (c) follow from (3.3) and (3.4).
3.3 An ascending chain of subgroups
With the group presentation from Proposition 3.3, we can describe Y as an ascending chain of subgroups.
Define
$Y_0$
to be the free group
$$ \begin{align} Y_0:=\langle S_m,S_{m+1},\ldots,S_{M-1}\,|\,\emptyset\rangle, \end{align} $$
and define
$Y_n$
to be the group with presentation
$$ \begin{align} Y_n:=\langle S_{m-n},S_{m-n+1},\ldots,S_{M+n-1}\; | \;R_{-n},\ldots,R_{n-1}\rangle \end{align} $$
for each positive integer n.
$Y_{n+1}$
is
$Y_n$
with two extra generators,
$S_{m-n-1}$
and
$S_{M+n}$
, and two extra relators,
$R_{-n-1}$
and
$R_n$
. It turns out that all of the appearances of
$S_{M+n}$
in
$R_{n}$
are contained in nested repeating patterns of words. Similarly, all of the appearances of
$S_{m-n-1}$
in
$R_{-n-1}$
are contained in nested repeating patterns of words. Given an explicit two-bridge link, one can find these patterns easily, as we did in Section 2 for
$L(17/13)$
, yet showing that these patterns exist for an arbitrary two-bridge link is much more complicated.
Once it is established that these patterns exist, however, it follows that for each nonnegative integer n,
$Y_{n+1}$
is
$Y_n$
after adjoining roots a finite number of times. This implies that each
$Y_n$
embeds into
$Y_{n+1}$
. Since Y is the direct limit of the sequence of
$Y_n$
’s, Y is the union of the ascending chain of
$Y_n$
’s. When the coefficients of
$\Delta _L$
are relatively prime, the elements whose roots are adjoining are homologically primitive.
The following lemma explicitly describes the relator
$R_n$
as nested patterns of repeating words. For simplicity of notation, let
$\delta =\pm 1$
.
Lemma 3.5 For each integer n, there exist a positive integer N, sequences of words in
$\mathcal{S}$
,
$$\begin{align*}\widehat{A}_0,\widehat{A}_1,\ldots,\widehat{A}_N, \end{align*}$$
$$\begin{align*}\widehat{V}_1,\ldots,\widehat{V}_N, \end{align*}$$
and
$$\begin{align*}\widehat{W}_1,\ldots,\widehat{W}_N, \end{align*}$$
and a sequence of positive integers
$n_1,\ldots ,n_N$
such that all of the following hold:
-
(M1)
$\widehat {A}_0$
is a cyclic permutation of
$R_n$
. -
(M2)
$\widehat {A}_N=S_{M+n}^{\delta }$
. -
(M3) For each
$i=1,\ldots ,N$
,
$$\begin{align*}\widehat{W}_i^{-1}\widehat{A}_{i-1}\widehat{W}_i=\widehat{A}_i^{n_i}\widehat{V}_i. \end{align*}$$
-
(M4) For each
$i=1,\ldots ,N$
,
$\widehat {V}_i$
and
$\widehat {W}_i$
are contained in the subgroup generated by the set
$$\begin{align*}\{S_{m+n},S_{m+n+1},\ldots,S_{M+n-1}\}. \end{align*}$$
-
(M5) For each
$i=1,\ldots ,N$
, there is some l with
$m<l\leq M$
and integers
$b_l,\ldots ,b_M$
(which depend on i) such that with
$$\begin{align*}[\widehat{A}_i]=\sum_{j=l}^Mb_jS^{\prime}_{j+n}=b_lS^{\prime}_{l+n}+b_{l+1}S^{\prime}_{l+n+1}+\cdots+b_MS^{\prime}_{M+n} \end{align*}$$
$|b_{l+j}|=|b_{M-j}|$
.
Also, there are sequences
and
such that:
-
(m1)
is a cyclic permutation of
$R_n$
. -
(m2)
. -
(m3) For each
$i=1,\ldots ,N$
, -
(m4) For each
$i=1,\ldots ,N$
,
and
are contained in the subgroup generated by the set
$$\begin{align*}\{S_{m+n+1},\ldots,S_{M+n-1},S_{M+n}\}. \end{align*}$$
-
(m5) For each
$i=1,\ldots ,N$
, there is some
$l'$
with
$m\leq l'< M$
, and integers
$b_m,\ldots ,b_{l'}$
(which depend on i) such that with
$|b_{m+j}|=|b_{l'-j}|$
.
Remark 3.6
$Y_1$
is obtained from
$Y_0$
by adding
$2N$
roots. In order of increasing index, each
$\widehat {A}_i$
is added as the
$n_i$
th root of some element, then each
is added as an
$n_i$
th root. The conditions (M5) and (m5) are used to show that the elements whose roots are added are homologically primitive.
Lemma 3.5 is proved in Section 5.7.
Proposition 3.7 The Alexander subgroup Y of any oriented two-bridge link is a union of an ascending chain of subgroups
$$\begin{align*}Y_0<Y_1<Y_2<\cdots<Y_i<\cdots<\bigcup_{n=1}^{\infty}Y_n\cong Y, \end{align*}$$
where
$Y_{n+1}$
is obtained from
$Y_n$
by adjoining a finite number of roots.
Proof Define the sequence
$Y_0,Y_1,Y_2,\ldots $
as in (3.5) and (3.6). Consider
$Y_n$
for some nonnegative integer n:
$$\begin{align*}Y_n=\langle S_{m-n},\ldots,S_{M+n-1}\; | \;R_{-n},\ldots,R_{n-1}\rangle \end{align*}$$
and
$$\begin{align*}Y_{n+1}=\langle S_{m-n-1},\ldots,S_{M+n}\; | \;R_{-n-1},\ldots,R_{n}\rangle. \end{align*}$$
By Lemma 3.5, there are an integer N, sequences of words
$$\begin{align*}\widehat{A}_0,\ldots,\widehat{A}_N, \end{align*}$$
$$\begin{align*}\widehat{V}_1,\ldots,\widehat{V}_N, \end{align*}$$
and
$$\begin{align*}\widehat{W}_1,\ldots,\widehat{W}_N, \end{align*}$$
and a sequence of integers
$$\begin{align*}n_1,\ldots,n_N \end{align*}$$
Let
$\langle t_i\rangle $
be an infinite cyclic group generated by
$t_i$
for each
$i=1,\ldots ,N$
. Also, let
$t_0$
be the identity element of
$Y_n$
.
Define
$$ \begin{align} H_0=Y_n, \end{align} $$
and for each
$i=1,\ldots ,N$
, recursively define
$$ \begin{align} H_i:=H_{i-1}\underset{\widehat{h}_i=t_i^{n_i}}{*}\langle t_i\rangle, \end{align} $$
where
$$ \begin{align} \widehat{h}_i=\widehat{W}_i^{-1}t_{i-1}\widehat{W}_i\widehat{V}_i^{-1}. \end{align} $$
We know that
$\widehat {h}_i$
is an element of
$H_{i-1}$
since
$\widehat {V}_i$
and
$\widehat {W}_i$
only use generators in
$\{S_{m+n},\ldots ,S_{M+n-1}\}$
by Lemma 3.5
(M4).
We can write the following presentation for
$H_N$
:
$$ \begin{align} H_{N}\cong\langle S_{m-n},\ldots,S_{M+n-1}, t_1,\ldots,t_N\; | \; R_{-n},\ldots,R_{n-1}, \{\widehat{h}_i^{-1}t_i^{n_i}\}_{i=1}^{N}\rangle. \end{align} $$
For each
$i=1,\ldots ,N$
,
$\widehat {h}_i^{-1}t_i^{n_i}=1$
, so by (3.9),
$$ \begin{align} 1=t_{i-1}^{-1}\widehat{W}_it_i^{n_i}\widehat{V}_i\widehat{W}_i^{-1}. \end{align} $$
Now, we find a new presentation of
$H_N$
by altering the one in (3.10). Since by Lemma 3.5
(M2),
$\widehat {A}_N$
is
$S_{M+n}^{\delta }$
, we can add the generator
$S_{M+n}$
and identify it with
$t_N^{\delta }$
by adding the relation
$t_N^{-1}\widehat {A}_N$
. By backward substitution using Lemma 3.5
(M3) and (3.11),
$$\begin{align*}t_{i-1}=\widehat{W}_i\widehat{A}_i^{n_i}\widehat{V}_i\widehat{W}_i^{-1}=\widehat{A}_{i-1} \end{align*}$$
for each
$i=N,\ldots ,1$
. Thus, each of the relations
$\widehat {h}_i^{-1}t_i^{n_i}$
in (3.10) is equivalent to
$t_i^{-1}A_i$
for
$i=0,\ldots ,N-1$
. In particular, since
$t_0$
is trivial,
$A_0=1$
. After these alterations,
$H_N$
has the following presentation:
$$\begin{align*}H_N\cong\langle S_{m-n},\ldots,S_{M+n}, t_1,\ldots,t_N\; | \; R_{-n},\ldots,R_{n-1},\widehat{A}_0, t_1^{-1}\widehat{A}_1, \ldots, t_N^{-1}\widehat{A}_N \rangle. \end{align*}$$
We can now use the relations
$t_1^{-1}\widehat {A}_1, \ldots , t_N^{-1}\widehat {A}_N$
to eliminate the generators
$t_1,\ldots , t_N$
. Since
$A_0$
is a cyclic permutation of
$R_n$
by Lemma 3.5
(M1),
$A_0$
can be replaced by
$R_n$
producing the following presentation:
$$\begin{align*}H_N\cong\langle S_{m-n},\ldots,S_{M+n}\; | \;R_{-n},\ldots,R_n\rangle. \end{align*}$$
Likewise, by Lemma 3.5, there are sequences of words
and
For each
$i=1,\ldots ,N$
, define
where
We can identify
$t_N$
with
which is
$S_{m-n-1}^{\delta }$
by Lemma 3.5
(m2). By backward substitution using (m1)–(m3) of Lemma 3.5,
Consider
$Y_n$
and
$Y_{n+1}$
for a nonnegative integer n. For each
$i=0,\ldots ,2N-1$
,
$H_i$
embeds into
$H_{i+1}$
since
$H_{i+1}$
is a free product of
$H_i$
and
$\mathbb{Z}$
amalgamated along infinite cyclic subgroups. Let
$\varphi _i:H_i\to H_{i+1}$
be the embedding which maps
$S_k\mapsto S_k$
and
$t_k\mapsto t_k$
for all k. The composition
$f_n=\varphi _{2N-1}\circ \cdots \circ \varphi _{0}$
is an embedding of
$Y_n$
into
$Y_{n+1}$
which maps
$S_k\mapsto S_k$
for all k.
Thus, we have the following sequence of embeddings:
The Alexander subgroup Y is the direct limit of this sequence. Since each
$f_n$
is an embedding, Y is a union of an ascending chain of subgroups as desired.
3.4 Proof of Lemma 1.6
We now turn our attention to proving Lemma 1.6. First, we state a more precise and detailed version of Lemma 1.6.
Lemma 3.8 Suppose that Y is the Alexander subgroup of a two-bridge link whose Alexander polynomial has relatively prime coefficients so that Y is an ascending chain of subgroups
$$\begin{align*}Y_0<Y_1<Y_2<\cdots<Y=\bigcup_{n=1}^{\infty}Y_n \end{align*}$$
as defined in (3.5) and (3.6). For each
$n:$
-
(a)
$Y_n$
is para-free of the rank
$M-m$
and -
(b)
$|Y_{n+1}:Y_n[Y_{n+1},Y_{n+1}]|=\underline {a}_g^2$
, where
$\underline {a}_g$
is the leading coefficient of the Alexander polynomial of L.
Proof First, we show (a).
$Y_0$
is a para-free of rank
$M-m$
since it is a rank
$M-m$
free group. Suppose that for some
$n\geq 0$
,
$Y_n$
is para-free of rank
$M-m$
. By Lemma 3.5, there is are integer N, sequences of words
$$\begin{align*}\widehat{A}_0,\ldots,\widehat{A}_N, \end{align*}$$
$$\begin{align*}\widehat{V}_1,\ldots,\widehat{V}_N, \end{align*}$$
and
$$\begin{align*}\widehat{W}_1,\ldots,\widehat{W}_N, \end{align*}$$
and a sequence of integers
$$\begin{align*}n_1,\ldots,n_N, \end{align*}$$
Define
$H_0,\ldots ,H_{2N}$
as in (3.7), (3.8), and (3.12), so
$H_{2N}\cong Y_{n+1}$
as in (3.13).
Suppose
$H_{k-1}$
is para-free of rank
$M-m$
for some k such that
$0<k\leq N$
, so
$H_{k-1}^{\textsf{ab}}\cong \mathbb{Z}^{M-m}$
. Define
$$\begin{align*}B:=\frac{H_{k-1}}{\langle \widehat{h}_k \rangle[H_{k-1},H_{k-1}]}\cong\mathbb{Z}^{M-m-1}\oplus\frac{\mathbb{Z}}{C\mathbb{Z}}\,, \end{align*}$$
where
$$\begin{align*}\widehat{h}_k=\widehat{W}_k^{-1}t_{k-1}\widehat{W}_k\widehat{V}_k^{-1} \end{align*}$$
and C is an integer. If
$B\cong \mathbb{Z}^{M-m-1}$
, then
$\widehat {h}_k$
is homologically primitive in
$H_{k-1}$
, and inductively, by Proposition 1.8, each
$H_k$
is para-free of rank
$M-m$
.
By Proposition 3.4,
$H^{\textsf{ab}}_0=Y^{\textsf{ab}}_n$
has a
$2n\times (2n+M-m)$
presentation matrix:
$$\begin{align*}\left( \begin{array}{ccccccccccccc} a_m & a_{m+1} & \cdots & a_{M-1} & a_M \\ & \ddots & & \ddots & & \ddots \\ & & a_m & a_{m+1} & \cdots & a_{M-1} & a_M \end{array}\right). \end{align*}$$
$H_{k-1}$
is
$H_0$
with the
$n_j$
root of
$\widehat {h}_j$
added for each
$j=1,\ldots ,k-1$
. Thus, B is
$H^{\textsf{ab}}_0$
after killing the classes
$[\widehat {h}_j^{-1}t_j^{n_j}]$
for each
$j=1,\ldots ,k-1$
and killing the class
$[\widehat {h}_k^{-1}]$
. B is generated by
$S^{\prime }_{m-n},\ldots ,S^{\prime }_{M+n-1},t^{\prime }_1,\ldots $
,
$t^{\prime }_{k-1}$
, where
$t^{\prime }_j$
is the class
$[t_j]$
. Using these generators, B has the following
$(2n+k)\times (2n+k+M-m-1)$
presentation matrix:
Applying the row operations
$\textbf{row}_{j}+n_{j+1}\textbf{row}_{j+1}\to \textbf{row}_j$
for each row
$j=2n+k-1,\ldots , 2n+1$
results in the matrix
where
$$\begin{align*}[U_j]=[\widehat{V}_j]+n_j([\widehat{V}_{j+1}]+n_{j+1}([\widehat{V}_{j+2}]+\cdots+n_{k-2}([\widehat{V}_{k-1}] +n_{k-1}[\widehat{V}_k])\cdots). \end{align*}$$
Eliminating the last
$k-1$
rows and columns results in the
$(2n+1)\times (2n+M-m)$
presentation matrix D:
$$\begin{align*}D=\left( \begin{array}{cccccccccccccc} a_m & a_{m+1} & \cdots & a_{M-1} & a_M \\ & a_m & a_{m+1} & \cdots & a_{M-1} & a_M \\ & & \ddots & & \ddots & & \ddots \\ & & & a_m & a_{m+1} & \cdots & a_{M-1} & a_M \\ & & & & c_{m} & c_{m+1} & \cdots & c_{M-1} \\ \end{array}\right), \end{align*}$$
where
$$\begin{align*}[U_1]=c_{m}S^{\prime}_{m+n} + c_{m+1}S^{\prime}_{m+n+1} + \cdots + c_{M-1}S^{\prime}_{M+n-1}. \end{align*}$$
By Lemma 3.5
(M5), for some l with
$m<l\leq M$
, there are integers
$b_l,\ldots ,b_M$
such that
$$ \begin{align} [\widehat{A}_k]=\sum_{j=l}^Mb_jS^{\prime}_{j+n} \end{align} $$
and
$|b_{l+j}|=|b_{M-j}|$
.
Claim 1 For each
$j=m,\ldots ,M-1$
,
$$\begin{align*}c_j=\left\{ \begin{array}{ll} a_{j}, & \text{when }m\leq j<l,\\ a_{j} - (\prod_{s=1}^kn_s)b_{j},& \text{when }l\leq j< M-1. \end{array} \right. \end{align*}$$
From the row operations,
$$ \begin{align*} [U_1]&=[\widehat{V}_1]+n_1([\widehat{V}_2]+n_2([\widehat{V}_3]+\cdots+n_{k-2}([\widehat{V}_{k-1}] +n_{k-1}[\widehat{V}_k])\cdots))\\ &=[\widehat{V}_1]+n_1[\widehat{V}_2]+n_1n_2[\widehat{V}_3]+\cdots+\left(\prod_{s=1}^{k-2}n_s\right)[\widehat{V}_{k-1}]+\left(\prod_{s=1}^{k-1}n_s\right)[\widehat{V}_k]\\ &=\sum_{j=1}^k\left(\prod_{s=1}^{j-1}n_s\right)[\widehat{V}_j]. \end{align*} $$
We use the convention that any empty product
$\prod _{j=1}^0(x_j)$
is 1. By Lemma 3.5
(M3),
$\widehat {V}_j=\widehat {A}_j^{-n_j}\widehat {W}_j^{-1}\widehat {A}_{j-1}\widehat {W}_j$
, so
$[\widehat {V}_j]=[\widehat {A}_{j-1}]-n_j[\widehat {A}_j]$
. Thus,
$$ \begin{align*} \sum_{j=1}^k\left(\prod_{s=1}^{j-1}n_s\right)[\widehat{V}_j]&=\sum_{j=1}^k\left(\prod_{s=1}^{j-1}n_s\right)([\widehat{A}_{j-1}]-n_j[\widehat{A}_j])\\ &=\sum_{j=1}^k\left(\prod_{s=1}^{j-1}n_s\right)[\widehat{A}_{j-1}]-\sum_{j=1}^k\left(\prod_{s=1}^jn_s\right)[\widehat{A}_j]\\ &=[\widehat{A}_0]-\left(\prod_{s=1}^kn_s\right)[\widehat{A}_k]. \end{align*} $$
Therefore, since
$\widehat {A}_0$
is a cyclic permutation of
$R_n$
by Lemma 3.5
(M1),
$$ \begin{align} [U_1]=[R_n]-\Bigg(\prod_{s=1}^kn_s\Bigg)[\widehat{A}_k]. \end{align} $$
The statement of the claim follows from Proposition 3.4 (a), (3.14), and (3.15).
By Lemma A.1, C is the
$\gcd $
of all the
$(2n+1)\times (2n+1)$
minors of D. Suppose a prime d divides C, so d divides the determinant of every
$(2n+1)\times (2n+1)$
minor of D. The determinant of the minor of D given by the first
$2n+1$
columns is
$a_m^{2n+1}$
, so d divides
$a_m$
.
Claim 2 There is some
$(2n+1)\times (2n+1)$
minor of D whose determinant is not divisible by d.
By Proposition 3.4
(c), the integers
$a_m,\ldots ,a_M$
are the coefficients of the Alexander polynomial. Since the coefficients of
$\Delta _L(t)$
are relatively prime, there is some coefficient that d does not divide. Let
$m+i$
be the minimal index such that d does not divide
$a_{m+i}$
. We prove this claim in two cases.
Case 1. Suppose at least one of the following holds:
-
•
$m+i<l$
, -
• d divides some
$n_s$
with
$s\leq k$
, or -
• d divides
$b_{j}$
for all
$j=l,\ldots ,i$
.
Then, either
$m+i<l$
or d must divide
$(\prod _{s=1}^kn_s)b_{j}$
for all
$j=l,\ldots ,m+i$
. By Claim 1, d divides
$c_j$
when
$j<m+i$
and d does not divide
$c_{m+i}$
.
Let E be the
$(2n+1)\times (2n+1)$
minor of D consisting of the
$n+1$
consecutive columns starting with the first column which with
$a_{m+i}$
(or
$c_{m+i}$
if
$n=0$
) at the top. Thus, working modulo d, we have the following minor:
$$\begin{align*}E=\left( \begin{array}{cccccc} a_{m+i} & * & * & \cdots & * & *\\ 0 & a_{m+i} & * & \cdots & * & *\\ 0 & 0 & a_{m+i} & \cdots & * & *\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & 0 & \cdots & a_{m+i} & *\\ 0 & 0 & 0 & \cdots & 0 & c_{m+i}\\ \end{array}\right). \end{align*}$$
Since d does not divide
$a_{m+i}$
or
$c_{m+i}$
, d cannot divide
$\det (E)$
.
Case 2. Suppose all of the following hold:
-
•
$l\leq m+i$
, -
• d does not divide any
$n_s$
with
$s\leq k$
, and -
• there is some
$j\leq m+i$
such that d does not divide
$b_j$
.
Let
$F_1$
be the
$(2n+1)\times 2n$
minor given by the
$2n$
consecutive columns with the coefficient
$a_{M-i}$
. By Proposition 3.4
(c),
$a_{m+j}=a_{M-j}$
for all
$j=0,\ldots ,M-m$
, so
$M-i$
is the maximal index such that d divides
$a_{M-i}$
. Thus, modulo d,
$F_1$
has the following form:
$$\begin{align*}F_1=\left( \begin{array}{ccccc} a_{M-i} & 0 & 0 & \cdots & 0\\ * & a_{M-i} & 0 & \cdots & 0\\ * & * & a_{M-i} & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ * & * & * & \cdots & a_{M-i}\\ * & * & * & \cdots & *\\ \end{array}\right). \end{align*}$$
We need to find a column in D with the first
$2n$
entries divisible by d and the last entry not divisible by d.
Let
$l+i'$
be the minimal index such that d does not divide
$b_{l+i'}$
, so
$l+i'\leq m+i$
.
Since d does not divide
$b_{l+i'}$
and
$b_{l+i'}=b_{M-i'}$
, d does not divide
$b_{M-i'}$
. By Lemma 3.5
(M4), for all j, the coefficient of
$S^{\prime }_{M+n}$
in
$[\widehat {V}_j]$
is zero, so by (3.15),
$$\begin{align*}a_M=b_M\prod_{s=1}^kn_s. \end{align*}$$
Since
$a_m=a_M$
and d divides
$a_m$
, d must also divide
$b_M$
. Therefore, d divides
$b_l$
, so
$i'>0$
and
$M-i'\leq M-1$
.
Since
$M-i'\leq M-1$
, there is some column
$F_2$
which ends with
$c_{M-i'}$
. Every other entry in
$F_2$
is 0 or
$a_j$
for some
$j>M-i'$
. Since
$l+i'\leq m+i$
and
$m<l$
,
$$\begin{align*}0 < l - m \leq i-i', \end{align*}$$
so
$M-i<M-i'$
. Thus, by Claim 1, d does not divide
$c_{M-i'}$
, and for all
$j>M-i'$
, d divides
$a_j$
.
Combine
$F_1$
and
$F_2$
to get a
$(2n+1)\times (2n+1)$
minor F of D. Working modulo d, we have the minor:
$$\begin{align*}F=\left( \begin{array}{cccccc} a_{M-i} & 0 & 0 & \cdots & 0 & 0\\ * & a_{M-i} & 0 & \cdots & 0 & 0\\ * & * & a_{M-i} & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ * & * & * & \cdots & a_{M-i} & 0\\ * & * & * & \cdots & * & c_{M-i'}\\ \end{array}\right). \end{align*}$$
Since d does not divide
$a_{M-i}$
or
$c_{M-i'}$
, d cannot divide
$\det (F)$
.
In conclusion, there are no primes which divide every determinant of
$(2n+1)\times (2n+1)$
submatrices of D, so
$C=1$
. Thus,
$B\cong \mathbb{Z}^{M-m-1}$
, and
$H_k$
is para-free of rank
$M-m$
. By induction,
$H_N$
is para-free of rank
$M-m$
.
By a similar induction argument,
$H_N,\ldots ,H_{2N}$
are also para-free of rank
$M-m$
. Therefore,
$Y_{n+1}\cong H_{2N}$
is para-free of rank
$M-m$
, so by induction
$Y_n$
is para-free of rank
$M-m$
for each nonnegative integer n.
For (b), consider the group
$Y_{n+1}/Y_n[Y_{n+1},Y_{n+1}]$
, which is an abelian group with the following presentation:
$$\begin{align*}\frac{Y_{n+1}}{Y_n[Y_{n+1},Y_{n+1}]}\cong \langle S^{\prime}_{m-n-1},\ldots,S^{\prime}_{M+n}\; | \;[R_{-n-1}],\ldots,[R_{n}],S^{\prime}_{m-n},\ldots,S^{\prime}_{M+n-1}\rangle. \end{align*}$$
By Proposition 3.4,
$$\begin{align*}[R_j]=\underline{a}_gS^{\prime}_{M+j}+\underline{a}_{g-1}S^{\prime}_{M-1+j}+\cdots+\underline{a}_{g-1}S^{\prime}_{m+1+j}+\underline{a}_gS^{\prime}_{m+j}. \end{align*}$$
After eliminating the generators
$S^{\prime }_{m-n},\ldots ,S^{\prime }_{M+n-1}$
, we have that
$$\begin{align*}\frac{Y_{n+1}}{Y_n[Y_{n+1},Y_{n+1}]}\cong \langle S^{\prime}_{m-n-1},S^{\prime}_{M+n}\; | \;\underline{a}_gS^{\prime}_{M-n-1}, \underline{a}_gS^{\prime}_{m+n}\rangle, \end{align*}$$
so
$$\begin{align*}\Big|Y_{n+1}/Y_n[Y_{n+1},Y_{n+1}]\Big|=\left|\frac{\mathbb{Z}}{\underline{a}_g\mathbb{Z}}\oplus\frac{\mathbb{Z}}{\underline{a}_g\mathbb{Z}}\right|=\underline{a}_g^2. \end{align*}$$
4 Cycle graphs
Explicitly, Lemma 3.5 is about nested patterns of repeating words in the relator
$R_0$
. However, this pattern is inherited from patterns in the sequences of
$\epsilon _i$
’s and
$\sigma _i$
’s defined in (3.1) and (3.2). In the spirit of Hirasawa and Murasugi [Reference Hirasawa and Murasugi11], graphs are used in order to gain intuition about how the sequences of
$\epsilon _i$
’s and
$\sigma _i$
’s behave; however, the construction here slightly differs from the one Hirasawa and Murasugi used.
4.1 Incremental paths and cycles
A graded directed graph is a connected directed graph
$\Gamma $
with map
$\textsf{gr}:V(\Gamma )\to \mathbb{Z}$
called the grading. Here,
$V(\Gamma )$
denotes the set of vertices of
$\Gamma $
. Two graded directed graphs
$\Gamma $
and
$\Gamma '$
are isomorphic if there is a directed graph isomorphism
$f:\Gamma \to \Gamma '$
such that for every vertex P in
$\Gamma $
,
$\textsf{gr}(f(P))=\textsf{gr}(P)$
.
$\Gamma $
and
$\Gamma '$
are called relatively isomorphic if there is a directed graph isomorphism
$f:\Gamma \to \Gamma '$
and an integer k such that for every vertex P in
$\Gamma $
,
$\textsf{gr}(f(P))=\textsf{gr}(P)+k$
.
An incremental path is a graded directed path graph
$\Gamma $
where the gradings of adjacent vertices differ by
$\pm 1$
. Similarly, an incremental cycle is a graded directed cycle graph
$\Gamma $
where the gradings of adjacent vertices differ by
$\pm 1$
. An edge
$(P,P')$
in an incremental path or cycle is positive if
$\textsf{gr}(P')-\textsf{gr}(P)=+1$
and negative if
$\textsf{gr}(P')-\textsf{gr}(P)=-1$
.
Example 4.1 Let
$\Gamma $
be a directed graph with five vertices
$P_1,\ldots ,P_5$
, and edges
$(P_1,P_2),\ldots , (P_4,P_5)$
. Define a grading on the vertices as follows:
$$\begin{align*}\textsf{gr}(P_1)=0, \textsf{gr}(P_2)=1, \textsf{gr}(P_3)=2, \textsf{gr}(P_4)=1, \textsf{gr}(P_5)=2. \end{align*}$$
$\Gamma $
is an incremental path (see Figure 4).
Figure 4: The incremental path
$\Gamma $
.
Let
$\Gamma $
and
$\Gamma '$
be two incremental paths in which the grading of the last vertex in
$\Gamma $
is equal to the grading of the first vertex in
$\Gamma '$
. Define the concatenation of
$\Gamma $
and
$\Gamma '$
, denoted
$\Gamma *\Gamma '$
, to be the graded directed graph obtained by identifying the last vertex in
$\Gamma $
with the first vertex in
$\Gamma '$
(see Figure 5).
Figure 5: The concatenation of
$\Gamma $
and
$\Gamma '$
.
If the gradings of the first and last vertices in
$\Gamma $
are the same,
$\Gamma $
is called closable and the closure of
$\Gamma $
,
$\textsf{cl}(\Gamma )$
, is defined to be the incremental cycle obtained by identifying the first and last vertices in
$\Gamma $
.
4.2 Cycle graphs of co-prime pairs
Ultimately, Lemma 3.5 is a statement about the sequences of
$\epsilon _i$
’s and
$\sigma _i$
’s for co-prime pairs of integers. As computed in Proposition 3.2, the ith S-generator in
$R_0$
is determined by the values of
$\sigma _{2i-1}$
and
$\sigma _{2i}$
. Here, we construct a graph to analyze the sequences of
$\epsilon _i$
’s and
$\sigma _i$
’s.
We call a pair of integers
$(p,q)$
a relevant co-prime pair if p and q are co-prime, q is odd, and
$p>|q|>0$
. Define the sequences
$\epsilon _i$
and
$\sigma _i$
as in (3.1) and (3.2) for each integer i. Define the incremental path
$\Gamma (p,q)$
as follows: The vertex set of
$\Gamma (p,q)$
is
$\{P_0,\ldots ,P_{2p}\}$
, and the edge set of
$\Gamma (p,q)$
is
$$ \begin{align*} E(\Gamma(p,q))=\{(P_0,P_1),(P_1,P_2),\ldots,(P_{2p-1},P_{2p})\}. \end{align*} $$
The grading of each vertex is defined by
$\textsf{gr}(P_i)=\sigma _i$
.
$\Gamma (p,q)$
is always closable, and the cycle graph of p and q,
$\overline {\Gamma }(p,q)$
, is defined to be
$\textsf{cl}(\Gamma (p,q))$
. When studying
$\overline {\Gamma }(p,q)$
, it is convenient to think of its vertices
$\{P_0,\ldots ,P_{2p-1}\}$
being indexed by elements of
$\mathbb{Z}/(2p\mathbb{Z})$
. See Figure 6 for example.
Figure 6:
$\overline {\Gamma }(33,23)$
.
Proposition 4.2 Let
$(p,q)$
be a relevant co-prime pair. The cycle graphs
$\overline {\Gamma }(p,q)$
and
$\overline {\Gamma }(p,-q)$
are relatively isomorphic.
Proof Let
$\{\epsilon _i\}_{i\in \mathbb{Z}}$
be the sequence of signs of
$(p,q)$
defined in (3.1). For each integer i, define
$$\begin{align*}\varepsilon_i:=(-1)^{\lfloor \frac{-iq}{p}\rfloor}, \end{align*}$$
which is the sequence of signs of
$(p,-q)$
. Let
$q'$
be the unique integer such that
$0<q'<2p$
and
$q'q\equiv p-1$
modulo
$2p$
, so
$q'q=p-1+2pk$
for some integer k.
We claim that the following equivalence holds:
$$ \begin{align} \varepsilon_i=\epsilon_{i+q'}. \end{align} $$
Consider the following computation:
$$\begin{align*}\Big\lfloor \frac{-iq}{p}\Big\rfloor= \begin{cases} -\lfloor \frac{iq}{p}\rfloor, & iq\,\textsf{mod}\, p= 0, \\ -\lfloor \frac{iq}{p}\rfloor-1, & iq\,\textsf{mod}\, p\neq 0, \end{cases} \end{align*}$$
$$ \begin{align*} \Big\lfloor \frac{(i+q')q}{p}\Big\rfloor= \Big\lfloor \frac{iq+q'q}{p}\Big\rfloor= \Big\lfloor \frac{iq+p-1+2pk}{p}\Big\rfloor&= \Big\lfloor \frac{iq-1}{p}\Big\rfloor+2k+1\\ &= \begin{cases} \lfloor \frac{iq}{p}\rfloor+2k, & iq\,\textsf{mod}\, p= 0,\\ \lfloor \frac{iq}{p}\rfloor+2k+1, & iq\,\textsf{mod}\, p\neq 0. \end{cases} \end{align*} $$
We get the following equivalences modulo 2:
$$ \begin{align*} -\Big\lfloor \frac{iq}{p}\Big\rfloor &\equiv \Big\lfloor \frac{iq}{p}\Big\rfloor+2k, & (\textsf{mod}\,2)\\ -\Big\lfloor \frac{iq}{p}\Big\rfloor-1 &\equiv \Big\lfloor \frac{iq}{p}\Big\rfloor+1+2k. & (\textsf{mod}\,2) \end{align*} $$
Thus,
$$\begin{align*}(-1)^{\lfloor\frac{-iq}{p}\rfloor}=(-1)^{\lfloor \frac{(i+q')q}{p}\rfloor}. \end{align*}$$
For each integer
$i=0,\ldots ,2p$
, define
$$\begin{align*}\varsigma_i:= \sum_{j=0}^{i-1}\varepsilon_i , \end{align*}$$
which are the gradings of the vertices of
$\overline {\Gamma }(p,-q)$
. By (4.1),
$$\begin{align*}\varsigma_i=\sigma_{i+q'}-\sigma_{q'} \end{align*}$$
for every positive integer i. Since the
$\sigma _i$
’s are the gradings of the vertices of
$\overline {\Gamma }(p,q)$
, it follows that
$\overline {\Gamma }(p,q)$
and
$\overline {\Gamma }(p,-q)$
are relatively isomorphic.
4.3 Structure of cycle graphs
Given an incremental cycle
$\Gamma $
, a positive(negative) k-segment is a set of k consecutive positive(negative) edges in
$\Gamma $
which are followed and preceded by negative(positive) edges (see Figure 7a). For each relevant co-prime integer pair
$(p,q)$
,
$\overline {\Gamma }(p,q)$
is the closure of the concatenation of segments of alternating sign as follows:
$$\begin{align*}\overline{\Gamma}(p,q)=\textsf{cl}(\Lambda_0*\Lambda_1*\cdots*\Lambda_{n-1}). \end{align*}$$
As a convention, let
$\Lambda _0$
denote the segment in
$\overline {\Gamma }(p,q)$
containing the edge
$(P_0,P_1)$
.
Figure 7: Examples of a segment and a block.
Propositions 4.3 and 4.4 are analogs of the properties proved in Section 6 of Hirasawa and Murasugi’s paper [Reference Hirasawa and Murasugi11].
Proposition 4.3 Let
$(p,q)$
be a relevant co-prime pair with
$q>0$
. Denote the vertices of
$\overline {\Gamma }(p,q)$
by
$P_0,\ldots ,P_{2p-1}$
as defined in Section 4.2, and let
$$\begin{align*}\overline{\Gamma}(p,q)=\textsf{cl}(\Lambda_0*\Lambda_1*\cdots*\Lambda_{n-1}), \end{align*}$$
where
$\Lambda _0,\ldots ,\Lambda _{n-1}$
are segments. Also, let
$\kappa $
and
$\xi $
be integers such that
$p=\kappa q+\xi $
and
$0\leq \xi <q$
:
-
(a) The number of segments n in
$\overline {\Gamma }(p,q)$
is equal to
$2q$
. -
(b)
$P_i$
is at the beginning of a segment precisely when
$iq\,\textsf{mod}\, p <q$
. -
(c)
$P_i$
is at the beginning of a
$\kappa $
-segment precisely when
$\xi \leq iq\,\textsf{mod}\, p <q$
, and
$P_i$
is at the beginning of a
$(\kappa +1)$
-segment precisely when
$iq\,\textsf{mod}\, p <\xi $
. -
(d)
$\Lambda _0$
is a positive
$(\kappa +1)$
-segment. -
(e) The number of
$(\kappa +1)$
-segments in
$\overline {\Gamma }(p,q)$
is
$2\xi $
.
Proof For (a), the number of segments in
$\overline {\Gamma }(p,q)$
corresponds to the number of distinct floored quotients
$\lfloor \frac {iq}{p}\rfloor $
there are when
$i=0,\ldots ,2p-1$
. Since
$p>q$
, these quotients range from
$0$
to
$2q-1$
without skipping, so there are exactly
$2q$
segments.
A segment begins precisely when
$$\begin{align*}\lfloor\frac{(i-1)q}{p}\rfloor\neq\lfloor\frac{iq}{p}\rfloor, \end{align*}$$
which happens when
$(iq\,\textsf{mod}\, p)< q$
, proving (b).
For (c), suppose
$P_i$
is the beginning of a k-segment. k is the smallest positive integer such that
$$\begin{align*}\lfloor\frac{iq}{p}\rfloor\neq\lfloor\frac{(i+k)q}{p}\rfloor , \end{align*}$$
so
$$\begin{align*}(iq\,\textsf{mod}\, p) + (k - 1)q< p \end{align*}$$
and
$$\begin{align*}(iq\,\textsf{mod}\, p) + kq \geq p. \end{align*}$$
When
$\xi \leq (iq\,\textsf{mod}\, p) < q$
,
$k=\kappa $
. Likewise, when
$(iq\,\textsf{mod}\, p)<\xi $
,
$k=\kappa +1$
.
Since
$P_i$
is the beginning of a segment,
$iq\,\textsf{mod}\, p <q$
, so exactly one of either
${\xi \leq (iq\,\textsf{mod}\, p) < q}$
or
$(iq\,\textsf{mod}\, p)<\xi $
is true. This determines precisely when
$\kappa $
- and
$(\kappa +1)$
-segments occur.
For part (d), it follows from (c) that
$\Lambda _0$
is a
$(\kappa +1)$
-segment. Since
$\epsilon _0$
is positive,
$\Lambda _0$
is a positive segment.
When
$q=1$
,
$\epsilon _i=1$
for
$0\leq i < p$
and
$\epsilon _i=-1$
for
$p\leq i < 2p$
. Thus,
$\overline {\Gamma }(p,q)$
is the concatenation of two
$\kappa $
-segments. When
$q>1$
,
$\overline {\Gamma }(p,q)$
has more interesting structure.
A k-block of length l in
$\overline {\Gamma }(p,q)$
is a sequence of l consecutive k-segments that is not preceded or followed by a k-segment (see Figure 7b). A k-block of length
$1$
is called an isolated block.
Proposition 4.4 Let
$(p,q)$
be a relevant co-prime pair with
$q>1$
, and let
$P_0,\ldots ,P_{2p-1}$
be the vertices of
$\overline {\Gamma }(p,q)$
as defined in Section 4.2. Let
$\kappa $
,
$\xi $
,
$\kappa '$
, and
$\xi '$
be integers such that
$$ \begin{align} p=\kappa q+\xi\text{ with }0<\xi<q \end{align} $$
and
$$ \begin{align} q=\kappa'\xi+\xi'\text{ with }0\leq\xi'<\xi. \end{align} $$
-
(a) All of the
$\kappa $
-blocks in
$\overline {\Gamma }(p,q)$
have length
$\kappa '$
or
$\kappa '-1$
. -
(b) If
$P_j$
is the start of a
$\kappa $
-block, then when the
$$\begin{align*}q-\xi'\leq jq\,\textsf{mod}\, p < q , \end{align*}$$
$\kappa $
-blocks have length
$\kappa '$
and when the
$$\begin{align*}q-\xi\leq jq\,\textsf{mod}\, p < q-\xi' , \end{align*}$$
$\kappa $
-blocks have length
$\kappa '-1$
.
-
(c) If
$\kappa '\geq 2$
, then all the
$(\kappa +1)$
-blocks in
$\overline {\Gamma }(p,q)$
are isolated. -
(d) If
$\kappa '=1$
, then all the
$\kappa $
-blocks in
$\overline {\Gamma }(p,q)$
are isolated.
Proof Similar to the proof of Proposition 4.3, this proposition is just a matter of determining when
$\kappa $
-blocks and
$(\kappa +1)$
-blocks appear in
$\overline {\Gamma }(p,q)$
.
Suppose
$P_i$
is the beginning of a
$(\kappa +1)$
-segment. The next segment begins at
$P_j$
where
$j=i+\kappa +1$
, and by (4.2),
$$ \begin{align*} jq\,\textsf{mod}\, p&=((i+\kappa+1)q)\,\textsf{mod}\, p\\ &=(iq+\kappa q +q)\,\textsf{mod}\, p\\ &=(iq+p-\xi+q)\,\textsf{mod}\, p\\ &=((iq\,\textsf{mod}\, p)+q-\xi)\,\textsf{mod}\, p. \end{align*} $$
Since
$P_i$
is the beginning of a
$(\kappa +1)$
-segment,
$(iq\,\textsf{mod}\, p)<\xi $
by Proposition 4.3
(c), so
$$ \begin{align} q-\xi \leq (iq\,\textsf{mod}\, p)+q-\xi<q<p. \end{align} $$
Thus,
$$ \begin{align} jq\,\textsf{mod}\, p=(iq\,\textsf{mod}\, p)+q-\xi. \end{align} $$
For (a) and (b), suppose a
$\kappa $
-block starts at vertex
$P_j$
. The length of the
$\kappa $
-block starting at
$P_j$
is the smallest positive integer n, such that
$P_{s(n)}$
is the start of a
$(\kappa +1)$
-block where
$s(k)=j+k\kappa $
, so n is the smallest positive integer such that
$$\begin{align*}0\leq s(n)q\,\textsf{mod}\, p\xi < \xi. \end{align*}$$
By (4.2),
$$ \begin{align*} s(k)q\,\textsf{mod}\, p&=(j+k\kappa)q\,\textsf{mod}\, p\\ &=(jq+k\kappa q)\,\textsf{mod}\, p\\ &=(jq+kp-k\xi)\,\textsf{mod}\, p\\ &=((jq\,\textsf{mod}\, p)-k\xi)\,\textsf{mod}\, p. \end{align*} $$
By (4.4) and (4.5), since
$P_j$
is the beginning of a
$\kappa $
-segment,
$$\begin{align*}q-\xi\leq jq\,\textsf{mod}\, p < q. \end{align*}$$
We compute the length n for each of the two cases
$q-\xi \leq (jq\,\textsf{mod}\, p) < q-\xi ' $
and
$q-\xi '\leq (jq\,\textsf{mod}\, p) < q $
.
Suppose that
$$ \begin{align} q-\xi'\leq jq\,\textsf{mod}\, p < q. \end{align} $$
By (4.3),
$$\begin{align*}((jq\,\textsf{mod}\, p)-\kappa'\xi=((jq\,\textsf{mod}\, p)-q+\xi' \end{align*}$$
and
$$\begin{align*}0\leq ((jq\,\textsf{mod}\, p)-q+\xi'<\xi', \end{align*}$$
so
$$\begin{align*}0\leq s(\kappa')q\,\textsf{mod}\, p<\xi'<\xi. \end{align*}$$
Thus,
$n\leq \kappa '$
.
Suppose
$k\leq \kappa '-1$
. By (4.3) and (4.6),
$$ \begin{align*} \xi &\leq ((jq\,\textsf{mod}\, p)-q+\xi'+\xi\\ &=((jq\,\textsf{mod}\, p)-\kappa'\xi+\xi\\ &=((jq\,\textsf{mod}\, p)-(\kappa'-1)\xi, \end{align*} $$
so
$$\begin{align*}\xi\leq ((jq\,\textsf{mod}\, p)-k\xi<q. \end{align*}$$
Thus,
$$\begin{align*}\xi\leq s(k)q\,\textsf{mod}\, p<q, \end{align*}$$
so
$n\geq \kappa '$
. Therefore,
$n=\kappa '$
.
Suppose
$$\begin{align*}q-\xi\leq (jq\,\textsf{mod}\, p)< q-\xi'. \end{align*}$$
By (4.3),
$$\begin{align*}((jq\,\textsf{mod}\, p)-(\kappa'-1)\xi=((jq\,\textsf{mod}\, p)-q+\xi'+\xi \end{align*}$$
and
$$\begin{align*}0\leq \xi'\leq ((jq\,\textsf{mod}\, p)-q+\xi'+\xi<\xi, \end{align*}$$
so
$$\begin{align*}0\leq s(\kappa'-1)q\,\textsf{mod}\, p<\xi. \end{align*}$$
Thus,
$n\leq \kappa '-1$
.
Suppose
$k\leq \kappa '-2$
. By (4.3) and (4.6),
$$ \begin{align*} \xi &\leq ((jq\,\textsf{mod}\, p)-q+\xi'+2\xi\\ &=((jq\,\textsf{mod}\, p)-(\kappa'-2)\xi, \end{align*} $$
so
$$\begin{align*}\xi\leq ((jq\,\textsf{mod}\, p)-k\xi<q. \end{align*}$$
Thus,
$$\begin{align*}\xi\leq s(k)q\,\textsf{mod}\, p<q, \end{align*}$$
so
$n\geq \kappa '-1$
. Therefore,
$n=\kappa '-1$
. Thus, all of the
$\kappa $
-blocks have length
$\kappa '$
or
$\kappa '-1$
. For (c), suppose that
$\kappa '\geq 2$
. By (4.3),
$$\begin{align*}q-\xi=(\kappa'-1)\xi+\xi' , \end{align*}$$
and since
$\kappa '\geq 2$
,
$$\begin{align*}\xi\leq\xi+\xi'\leq q-\xi, \end{align*}$$
so by (4.4),
$$\begin{align*}\xi\leq (iq\,\textsf{mod}\, p)+q-\xi <q. \end{align*}$$
Thus, by (4.5),
$$\begin{align*}\xi\leq jq\,\textsf{mod}\, p <q. \end{align*}$$
By Proposition 4.3
(c),
$P_j$
must be the beginning of a
$\kappa $
-segment, so
$(\kappa +1)$
-segments cannot occur consecutively. Therefore,
$(\kappa +1)$
-blocks are isolated.
4.4 Reducing cycle graphs
Let
$(p,q)$
be a relevant co-prime pair with
$q>1$
. Let
$\kappa $
,
$\xi $
,
$\kappa '$
, and
$\xi '$
be defined as in Proposition 4.4, and decomposition
$\overline {\Gamma }(p,q)$
into segments
$\Lambda _0,\ldots ,\Lambda _{2q-1}$
as follows:
$$ \begin{align} \overline{\Gamma}(p,q)=\textsf{cl}(\Lambda_0*\cdots*\Lambda_{2q-1}). \end{align} $$
Again,
$\Lambda _0$
is the segment containing the edge
$(P_0,P_1)$
. By Proposition 4.3
(e),
$2\xi $
of the segments in (4.7) are
$(\kappa +1)$
-segments. Let
$j_0,\ldots ,j_{2\xi -1}$
be the indices in ascending order of the
$(\kappa +1)$
-segments in (4.7). Define a reduction of
$\overline {\Gamma }(p,q)$
, denoted
$R(\overline {\Gamma })(p,q)$
, to be the following graded directed cycle graph with
$2\xi $
vertices
$Q_0,\ldots , Q_{2\xi -1}$
with edge set
$$\begin{align*}\{(Q_0,Q_1),(Q_1,Q_2),\ldots,(Q_{2\xi-2},Q_{2\xi-1}),(Q_{2\xi-1},Q_0)\}. \end{align*}$$
Define
$\textsf{gr}(Q_0)=0$
. For each
$i=1,\ldots ,2\xi -1$
, define
$\textsf{gr}(Q_i):=\textsf{gr}(Q_{i-1})+1$
when
$\Lambda _{j_i}$
is a positive segment, and
$\textsf{gr}(Q_i):=\textsf{gr}(Q_{i-1})-1$
when
$\Lambda _{j_i}$
is a negative segment. Essentially,
$R(\overline {\Gamma })(p,q)$
is
$\overline {\Gamma }(p,q)$
with the
$\kappa $
-segments removed and the
$(\kappa +1)$
-segments replaced with edges according to the sign of the segment. For example, see Figure 8.
Figure 8: Reducing
$\overline {\Gamma }(33,23)$
.
Lemma 4.5 Let
$(p,q)$
be a relevant co-prime pair with
$q>1$
and
$\xi>1$
. Define
$p^*$
to be
$\xi $
, and define
$q^*$
as follows:
$$\begin{align*}q^*:=\left\{ \begin{array}{ll} \xi', & \text{when }\kappa'\text{ is even,}\\ \xi'-\xi, & \text{when }\kappa'\text{ is odd,} \end{array} \right. \end{align*}$$
-
(a)
$p^*$
is always positive and
$q^*$
is always odd. -
(b)
$R(\overline {\Gamma })(p,q)$
is isomorphic to
$\overline {\Gamma }(p^*,q^*)$
.
Proof For (a), clearly,
$p^*=\xi $
is positive. Also, notice that q is odd and
$$\begin{align*}\xi'=q-\kappa'\xi. \end{align*}$$
If
$\kappa '$
is even, then
$q^*=\xi '$
is odd. If
$\kappa '$
is odd, then
$\xi '$
and
$\xi $
must have opposite parities, so
$q^*=\xi '-\xi $
is odd.
For (b), consider
$\overline {\Gamma }(p,q)$
. By definition,
$R(\overline {\Gamma })(p,q)$
has
$2\xi $
edges and
$2\xi $
vertices. Let
$\{Q_0,\ldots ,Q_{2\xi -1}\}$
be the vertex set of
$R(\overline {\Gamma })(p,q)$
, and let
$\{P^*_0,\ldots ,P^*_{2\xi -1}\}$
be the vertex set of
$\overline {\Gamma }(p^*,q^*)$
. Since
$R(\overline {\Gamma })(p,q)$
and
$\overline {\Gamma }(p^*,q^*)$
are cycle graphs with the same number of vertices, there is an ungraded directed graph isomorphism between them mapping
$Q_i\mapsto P^*_i$
. Since
$\textsf{gr}(Q_0)$
and
$\textsf{gr}(P^*_0)$
are both 0 by definition, it only remains to show that
$$\begin{align*}\textsf{gr}(Q_{i+1})-\textsf{gr}(Q_i)=\textsf{gr}(P^*_{i+1})-\textsf{gr}(P^*_i) \end{align*}$$
for each
$i=0,\ldots ,2\xi -1$
.
For
$i=0,\ldots ,2\xi -1$
, define
$$ \begin{align*} \varepsilon_i:=\textsf{gr}(Q_{i+1})-\textsf{gr}(Q_i) \end{align*} $$
and
$$ \begin{align*} \eta_i:=(-1)^{\lfloor \frac{i\xi'}{\xi}\rfloor}. \end{align*} $$
If
$q^*=\xi '$
, then
$$\begin{align*}\textsf{gr}(P^*_{i+1})-\textsf{gr}(P^*_i)=\eta_i, \end{align*}$$
and if
$q^*=\xi '-\xi $
, then
$$\begin{align*}\textsf{gr}(P^*_{i+1})-\textsf{gr}(P^*_i)=(-1)^{\lfloor\frac{i(\xi'-\xi)}{\xi} \rfloor}=(-1)^i\eta_i. \end{align*}$$
Lt
$l_i$
be the index of the vertex in
$\overline {\Gamma }(p,q)$
at the beginning of
$\Lambda _{j_i}$
(see Figure 9). By definition of
$R(\overline {\Gamma })(p,q)$
,
$\varepsilon _i$
is positive precisely when
$\Lambda _{j_i}$
is a positive segment. Thus,
$\varepsilon _{i+1}=\varepsilon _i$
when
$\Lambda _{j_i}$
and
$\Lambda _{j_{i+1}}$
are separated by an even number of
$\kappa $
-segments, and
$\varepsilon _{i+1}=-\varepsilon _i$
when
$\Lambda _{j_i}$
and
$\Lambda _{j_{i+1}}$
are separated by an odd number of
$\kappa $
-segments. The desired result will follow from three claims.
Figure 9: The
$(\kappa +1)$
-segments of
$\overline {\Gamma }(17,5)$
. The indices of the segments are
$j_0=0$
,
$j_1=2$
,
$j_2=5$
, and
$j_3=7$
. The indices of the vertices at the beginning of each
$(\kappa +1)$
-segment are
$l_0=0$
,
$l_1=7$
,
$l_2=17$
, and
$l_3=24$
.
Claim 1 Whenever
$0\leq (i\xi '\,\textsf{mod}\,\xi )<\xi -\xi '$
,
$$\begin{align*}\eta_{i+1}=\eta_i, \end{align*}$$
and whenever
$(i\xi '\,\textsf{mod}\,\xi )\geq \xi -\xi '$
,
$$\begin{align*}\eta_{i+1}=-\eta_i. \end{align*}$$
When
$0\leq (i\xi '\,\textsf{mod}\,\xi )<\xi -\xi '$
, there are integers s and t with
$$\begin{align*}i\xi'= s\xi+t \text{ and } 0\leq t<\xi-\xi', \end{align*}$$
so
$$\begin{align*}s\xi\leq (i+1)\xi'=s\xi+t+\xi'<(s+1)\xi. \end{align*}$$
Thus,
$$\begin{align*}\eta_{i+1}=(-1)^{s}=\eta_i. \end{align*}$$
When
$(i\xi '\,\textsf{mod}\,\xi )\geq \xi -\xi '$
, there are integers s and t with
$$\begin{align*}i\xi'= s\xi+t \text{ and } \xi-\xi'\leq t<\xi, \end{align*}$$
so
$$\begin{align*}(s+1)\xi\leq (i+1)\xi'=s\xi+t+\xi'<(s+1)\xi+\xi'<(s+2)\xi. \end{align*}$$
Thus,
$$\begin{align*}\eta_{i+1}=(-1)^{s+1}=-\eta_i. \end{align*}$$
Claim 2 The segments
$\Lambda _{j_i}$
and
$\Lambda _{j_{i+1}}$
are separated by a
$\kappa $
-block of length
$\kappa '$
when
$$\begin{align*}\xi-\xi'\leq (l_iq\,\textsf{mod}\, p)<\xi \end{align*}$$
and a
$\kappa $
-block of length
$\kappa '-1$
(possibly zero) when
$$\begin{align*}0\leq (l_iq\,\textsf{mod}\, p)<\xi-\xi'. \end{align*}$$
By Proposition 4.4
(b), every
$\kappa $
-block begins at a vertex
$P_l$
where
$$\begin{align*}q-\xi\leq (lq\,\textsf{mod}\, p)<q. \end{align*}$$
The length of the block is
$\kappa '$
when
$$ \begin{align} q-\xi'\leq (lq\,\textsf{mod}\, p)<q, \end{align} $$
and the length is
$\kappa '-1$
when
$$ \begin{align} q-\xi \leq (lq\,\textsf{mod}\, p)<q-\xi'. \end{align} $$
The vertex at the end of the segment
$\Lambda _{j_i}$
is the same as the vertex at the beginning the segment
$\Lambda _{j_i+1}$
, so
$\Lambda _{j_i+1}$
begins at the vertex with index
$l':=l_i+\kappa +1$
. By Proposition 4.3
(b),
$$\begin{align*}0\leq l_iq\,\textsf{mod}\, p+q-\xi<q<p, \end{align*}$$
so
$$ \begin{align*} l'q\,\textsf{mod}\, p&=(l_i+\kappa+1)q\,\textsf{mod}\, p\\ &=(l_iq\,\textsf{mod}\, p+q-\xi)\,\textsf{mod}\, p \\ &=l_iq\,\textsf{mod}\, p+q-\xi. \end{align*} $$
By (4.8),
$\Lambda _{j_i}$
and
$\Lambda _{j_{i+1}}$
are separated by a
$\kappa $
-block of length
$\kappa '$
when
$$\begin{align*}q-\xi'\leq(l'q\,\textsf{mod}\, p)<q, \end{align*}$$
so
$$\begin{align*}\xi-\xi'\leq (l_iq\,\textsf{mod}\, p)<\xi. \end{align*}$$
By (4.9),
$\Lambda _{j_i}$
and
$\Lambda _{j_{i+1}}$
are separated by a
$\kappa $
-block of length
$\kappa '-1$
when
$$\begin{align*}q-\xi\leq(l'q\,\textsf{mod}\, p)<q-\xi', \end{align*}$$
so
$$\begin{align*}0\leq (l_iq\,\textsf{mod}\, p)<\xi-\xi'. \end{align*}$$
Claim 3 For each
$i=0,\ldots ,2\xi -1$
,
$$\begin{align*}l_iq\,\textsf{mod}\, p=i\xi'\,\textsf{mod}\,\xi. \end{align*}$$
$P_{l_i}$
and
$P_{l_{i+1}}$
are separated by a
$(\kappa +1)$
-segment and a
$\kappa $
-block. Therefore, when the length of the
$\kappa $
-block is
$\kappa '$
,
$$\begin{align*}l_{i+1}=l_i+(\kappa+1)+\kappa'\kappa, \end{align*}$$
so
$$ \begin{align*} l_{i+1}q\,\textsf{mod}\, p&=(l_iq+\kappa q+q+\kappa'\kappa q)\,\textsf{mod}\, p\\ &=(l_iq\,\textsf{mod}\, p+\xi'-\xi)\,\textsf{mod}\, p. \end{align*} $$
The last equality follows from (4.2) and (4.3). By Claim 2,
$$\begin{align*}0\leq l_iq\,\textsf{mod}\, p+\xi'-\xi<\xi'<p. \end{align*}$$
Therefore,
$$ \begin{align} l_{i+1}q\,\textsf{mod}\, p=l_iq\,\textsf{mod}\, p+\xi'-\xi. \end{align} $$
When the length of the
$\kappa $
-block is
$\kappa '-1$
,
$$\begin{align*}l_{i+1}=l_i+(\kappa + 1) + (\kappa'-1)\kappa=l_i+1+\kappa'\kappa, \end{align*}$$
so
$$ \begin{align*} l_{i+1}q\,\textsf{mod}\, p&=(l_iq+q+\kappa'\kappa q)\,\textsf{mod}\, p\\ &=(l_iq\,\textsf{mod}\, p+\xi')\,\textsf{mod}\, p. \end{align*} $$
By Claim 2,
$$\begin{align*}0<\xi'\leq l_iq\,\textsf{mod}\, p+\xi'<\xi<p. \end{align*}$$
Therefore,
$$ \begin{align} l_{i+1}q\,\textsf{mod}\, p=l_iq\,\textsf{mod}\, p+\xi'. \end{align} $$
If either (4.10) or (4.11) holds,
$$\begin{align*}l_{i+1}q\,\textsf{mod}\, p=(l_iq\,\textsf{mod}\, p +\xi')\,\textsf{mod}\, \xi, \end{align*}$$
so since
$l_0=0$
,
$$\begin{align*}l_iq\,\textsf{mod}\, p=i\xi'\,\textsf{mod}\,\xi \end{align*}$$
for each
$i=0,\ldots , 2\xi -1$
by induction. This completes the proof of the claim.
Suppose
$\kappa '$
is even. When
$\Lambda _{i+1}$
and
$\Lambda _i$
are separated by a
$\kappa $
-block of length
$\kappa '-1$
,
$\Lambda _{i+1}$
and
$\Lambda _i$
have the same sign, so
$$\begin{align*}\varepsilon_{i+1}=\varepsilon_i. \end{align*}$$
By the three claims,
$$\begin{align*}0\leq (i\xi'\,\textsf{mod}\,\xi)<\xi-\xi', \end{align*}$$
so
$$\begin{align*}\eta_{i+1}=\eta_i. \end{align*}$$
When
$\Lambda _{i+1}$
and
$\Lambda _i$
are separated by a
$\kappa $
-block of length
$\kappa '$
,
$\Lambda _{i+1}$
and
$\Lambda _i$
have opposite signs, so
$$\begin{align*}\varepsilon_{i+1}=-\varepsilon_i. \end{align*}$$
By the three claims,
$$\begin{align*}(i\xi'\,\textsf{mod}\,\xi)\geq\xi-\xi', \end{align*}$$
so
$$\begin{align*}\eta_{i+1}=-\eta_i. \end{align*}$$
Since
$\varepsilon _0=\eta _0=1$
, for every
$i=0,\ldots ,2\xi -1$
,
$$\begin{align*}\varepsilon_i=\eta_i, \end{align*}$$
so when
$q^*=\xi '$
,
$$\begin{align*}\textsf{gr}(P^*_{i+1})-\textsf{gr}(P^*_i)=\eta_i=\varepsilon_i=\textsf{gr}(Q_{i+1})-\textsf{gr}(Q_i). \end{align*}$$
Suppose
$\kappa '$
is odd. When
$\Lambda _{i+1}$
and
$\Lambda _i$
are separated by a
$\kappa $
-block of length
$\kappa '$
, then
$\varepsilon _{i+1}=\varepsilon _i$
. When
$\Lambda _{i+1}$
and
$\Lambda _i$
are separated by a
$\kappa $
-block of length
$\kappa '-1$
, then
$\varepsilon _{i+1}=-\varepsilon _i$
.
Thus, by the claims,
$\varepsilon _{i+1}=\varepsilon _i$
when
$\eta _{i+1}=-\eta _i$
, and
$\varepsilon _{i+1}=-\varepsilon _i$
when
$\eta _{i+1}=\eta _i$
. Again,
$\varepsilon _0=\eta _0=1$
. Therefore, for every
$i=0,\ldots ,2\xi -1$
,
$$\begin{align*}\varepsilon_i=(-1)^i\eta_i, \end{align*}$$
so when
$q^*=\xi '-\xi $
, then
$$\begin{align*}\textsf{gr}(P^*_{i+1})-\textsf{gr}(P^*_i)=(-1)^i\eta_i=\varepsilon_i=\textsf{gr}(Q_{i+1})-\textsf{gr}(Q_i). \end{align*}$$
Example 4.6 Consider the co-prime pair
$(33,23)$
.
$R(\overline {\Gamma })(33,23)$
is isomorphic to
$\Gamma (10,3)$
(see Figure 8).
4.5 Expanding cycle graphs
We can also reverse the reduction process. Let
$\Gamma $
be an incremental path with vertices
$P_0,\ldots ,P_n$
indexed such that
$(P_i,P_{i+1})$
is an edge in
$\Gamma $
for each
$i=0,\ldots ,n-1$
. Let s and b be positive integers, and let
$e=\pm 1$
. Define
$\tilde {E}(\Gamma ,s,b,e)$
to be the incremental path graph constructed as follows:
-
(1) Create an
$(s+1)$
-segment,
$\Lambda _i$
, for each edge
$(P_i,P_{i+1})$
in
$\Gamma $
. Choose
$\Lambda _i$
to be positive or negative according to the sign of the edge
$(P_i,P_{i+1})$
. -
(2) Between each pair
$\Lambda _i$
and
$\Lambda _{i+1}$
, for
$i=0,\ldots , n-2$
, add an s-block of length b or
$b-1$
. The length of the s-block is odd if the edges
$\Lambda _i$
and
$\Lambda _{i+1}$
have the same sign, and the length is even if
$\Lambda _i$
and
$\Lambda _{i+1}$
have opposite signs. Also, the first s-segment in the block has sign opposite of the sign of
$\Lambda _i$
. -
(3) Add another s-block to the beginning of
$\Lambda _0$
of length b or
$b-1$
depending on the signs of
$\Lambda _0$
and e following the same convention as the previous step. Also, the first s-segment in the block has sign opposite of e. -
(4) Finally, set the grading of the first vertex
$Q_0$
as follows: (4.12)
$$ \begin{align} \textsf{gr}(Q_0)=\left\{ \begin{array}{ll} \textsf{gr}(P_0)+s, & \text{when } e\text{ and }(P_0,P_1)\text{ are both positive,}\\ \textsf{gr}(P_0)-s, & \text{when } e\text{ and }(P_0,P_1)\text{ are both negative,}\\ \textsf{gr}(P_0), & \text{when } e\text{ and }(P_0,P_1)\text{ have opposite sign.}\\ \end{array} \right. \end{align} $$
For example, see Figure 10.
Figure 10: Expanding an incremental path.
We begin by investigating the gradings of the vertices in
$\tilde {E}(\Gamma ,s,b,e)$
.
Lemma 4.7 Let
$Q_0$
be the vertex at the beginning of
$\tilde {E}(\Gamma ,s,b,e)$
. For
$i=1,\ldots ,n$
, let
$Q_{i}$
be the vertex at the end of
$(s+1)$
-segment
$\Lambda _{i-1}$
as in the definition of
$\tilde {E}$
. For each
$i=1,\ldots ,n$
:
-
(a) If the signs of
$\Lambda _{i-1}$
and e are the same, then
$$\begin{align*}\textsf{gr}(Q_i)-\textsf{gr}(Q_0)=\textsf{gr}(P_i)-\textsf{gr}(P_0). \end{align*}$$
-
(b) If
$\Lambda _{i-1}$
is positive and e is negative, then
$$\begin{align*}\textsf{gr}(Q_i)-\textsf{gr}(Q_0)=\textsf{gr}(P_i)-\textsf{gr}(P_0)+s. \end{align*}$$
-
(c) If
$\Lambda _{i-1}$
is negative and e is positive, then
$$\begin{align*}\textsf{gr}(Q_i)-\textsf{gr}(Q_0)=\textsf{gr}(P_i)-\textsf{gr}(P_0)-s. \end{align*}$$
Proof Let
$\Gamma '$
be the subgraph of
$\tilde {E}(\Gamma ,s,b,e)$
starting at
$Q_0$
and ending at
$Q_i$
.
$\Gamma '$
is the concatenation of sum number of
$(s+1)$
- and s-segments. Let
$D^+$
and
$D^-$
be the number of positive or, respectively, negative
$(s+1)$
-segments in
$\Gamma '$
. Likewise, let
$d^+$
and
$d^-$
be the number of positive or, respectively, negative s-segments in
$\Gamma '$
. Note that
$D^+$
and
$D^-$
are also the number of positive and negative edges separating
$P_0$
and
$P_i$
in
$\Gamma $
, so
$$\begin{align*}D^+-D^-=\textsf{gr}(P_i)-\textsf{gr}(P_0). \end{align*}$$
Suppose
$\Lambda _{i-1}$
and e have the same sign, then the number of positive segments in
$\Gamma '$
is equal to the number of negative segments, so
$$\begin{align*}D^++d^+=D^-+d^-. \end{align*}$$
Thus,
$$ \begin{align*} \textsf{gr}(Q_i)-\textsf{gr}(Q_0)&=D^+(s+1)-D^-(s+1)+d^+s-d^-s\\ &=(D^++d^+)s-(D^-+d^-)s+D^+-D^-\\ &=D^+-D^-\\ &=\textsf{gr}(P_i)-\textsf{gr}(P_0). \end{align*} $$
Suppose
$\Lambda _{i-1}$
is positive and e is negative, then the total number of positive segments in
$\Gamma '$
is one more than the total number of negative segments, so
$$ \begin{align*} \textsf{gr}(Q_i)-\textsf{gr}(Q_0)&=D^+(s+1)-D^-(s+1)+d^+s-d^-s\\ &=(D^++d^+)s-(D^-+d^-)s+D^+-D^-\\ &=s+D^+-D^-\\ &=\textsf{gr}(P_i)-\textsf{gr}(P_0)+s. \end{align*} $$
Suppose
$\Lambda _{i-1}$
is negative and e is positive, then the total number of positive segments in
$\Gamma '$
is one less than the total number of negative segments, so
$$ \begin{align*} \textsf{gr}(Q_i)-\textsf{gr}(Q_0)&=D^+(s+1)-D^-(s+1)+d^+s-d^-s\\ &=(D^++d^+)s-(D^-+d^-)s+D^+-D^-\\ &=-s+D^+-D^-\\ &=\textsf{gr}(P_i)-\textsf{gr}(P_0)-s.\\[-34pt] \end{align*} $$
From this, we can show that concatenation behaves well under expansion.
Lemma 4.8 Suppose
$\Gamma $
and
$\Gamma '$
are incremental paths where the last vertex in
$\Gamma $
has the same grading as the first vertex in
$\Gamma '$
. Let
$e'$
be the sign of the last edge in
$\Gamma $
. For any positive integers s and b and any sign
$e=\pm 1$
,
$$\begin{align*}\tilde{E}(\Gamma*\Gamma',s,b,e)\cong\tilde{E}(\Gamma,s,b,e)*\tilde{E}(\Gamma',s,b,e'). \end{align*}$$
Proof The conclusion will be true by definition of the expansion procedure as long as
$\tilde {E}(\Gamma ,s,b,e)$
and
$\tilde {E}(\Gamma ',s,b,e')$
can be concatenated. Thus, our goal is to show that the last vertex in
$\tilde {E}(\Gamma ,s,b,e)$
has the same grading as the first vertex in
$\tilde {E}(\Gamma ',s,b,e')$
. This can be done by computing the gradings of
$\tilde {E}(\Gamma *\Gamma ',s,b,e)$
for many cases depending on the signs of e, the last edge in
$\Gamma $
, and the first edge in
$\Gamma '$
.
For example, suppose e, the last edge in
$\Gamma $
, and the first edge in
$\Gamma '$
are all positive. Let
$P_0$
and
$P_n$
be the first and last vertices of
$\Gamma $
. Let
$P^{\prime }_0$
be the first vertex in
$\Gamma '$
so
$\textsf{gr}(P_n)=\textsf{gr}(P^{\prime }_0)$
. Let
$Q_0$
and
$Q_n$
be the first and last vertices of
$\tilde {E}(\Gamma ,s,b,e)$
. Finally, let
$Q^{\prime }_0$
be the first vertex in
$\tilde {E}(\Gamma ',s,b,e')$
.
By (4.12),
$$\begin{align*}\textsf{gr}(Q^{\prime}_0)=\textsf{gr}(P^{\prime}_0)+s=\textsf{gr}(P_n)+s. \end{align*}$$
By Lemma 4.7,
$$ \begin{align*} \textsf{gr}(Q_n)&=\textsf{gr}(P_n)-\textsf{gr}(P_0)+\textsf{gr}(Q_0)\\ &=\textsf{gr}(Q^{\prime}_0)-s-\textsf{gr}(P_0)+\textsf{gr}(P_0)+s\\ &=\textsf{gr}(Q^{\prime}_0). \end{align*} $$
The proofs of all the other cases are similar.
Let
$\Gamma $
be a closable incremental path, and let e be the sign of the last edge in
$\Gamma $
. For any two positive integers s and b, define
$$\begin{align*}E(\Gamma,s,b):=\tilde{E}(\Gamma,s,b,e). \end{align*}$$
When
$\Gamma $
is closable,
$E(\Gamma ,s,b)$
is also closable.
Suppose
$\Gamma '$
is a closable incremental path such that
$\textsf{cl}(\Gamma )\cong \textsf{cl}(\Gamma ')$
. By construction,
$$ \begin{align} \textsf{cl}(E(\Gamma,s,b))\cong\textsf{cl}(E(\Gamma',s,b)) \end{align} $$
for all positive integers s and b.
For an incremental cycle
$\overline {\Gamma }$
, define
$$\begin{align*}E(\overline{\Gamma},s,b):=\textsf{cl}(E(\Gamma,s,b)), \end{align*}$$
where
$\Gamma $
is any incremental path such that
$\textsf{cl}(\Gamma )\cong \overline {\Gamma }$
. By (4.13),
$E(\overline {\Gamma },s,b)$
is well defined.
Reduction and expansion are naturally opposite operations.
Proposition 4.9 Suppose
$(p,q)$
is a relevant co-prime pair with
$q>1$
. Define
$\kappa $
and
$\kappa '$
as in (4.2) and (4.3):
$$\begin{align*}E(R(\overline{\Gamma})(p,q),\kappa,\kappa')\cong\overline{\Gamma}(p,q). \end{align*}$$
Proof By Proposition 4.3,
$\overline {\Gamma }(p,q)$
is the concatenation of
$\kappa $
-segments and
$(\kappa +1)$
-segments. The reduction R replaces
$(\kappa +1)$
-segments with single edges of the same sign. The expansion E transforms all the edges back into
$(\kappa +1)$
-segments.
By Proposition 4.4
(a), the
$(\kappa +1)$
-segments of
$\overline {\Gamma }(p,q)$
are separated by
$\kappa $
-blocks of length
$\kappa '$
or
$\kappa '-1$
(possibly zero). The blocks in
$\overline {\Gamma }(p,q)$
have even length precisely when the preceding and following
$(\kappa +1)$
-segments have opposite sign.
R removes these
$\kappa $
-blocks, and E restores them. The signs of consecutive edges in
$R(\overline {\Gamma }(p,q))$
correspond to the signs of the preceding and following
$(\kappa +1)$
-segments in
$\overline {\Gamma }(p,q)$
, so the length of each
$\kappa $
-block after the expansion will be the same as it was before the reduction.
It remains to check that gradings are preserved. Consider the edge in
$R(\overline {\Gamma }(p,q))$
corresponding to
$\Lambda _0$
in
$\overline {\Gamma }(p,q)$
as labeled in (4.7). Label the vertices at the beginning and end of this edge
$P_0$
and
$P_1$
, respectively.
By the definition of R, the grading of
$P_0$
is equal to the grading of the vertex at the beginning of
$\Lambda _0$
.
Consider
$\Lambda ^{\prime }_0$
, the
$(\kappa +1)$
-segment resulting from expansion of the edge after
$P_0$
. Let
$Q_0$
be the grading at the end of the
$\Lambda ^{\prime }_0$
as in Lemma 4.7, and let
$Q^{\prime }_1$
be the vertex at the beginning of
$\Lambda ^{\prime }_0$
.
Now, we show that
$\textsf{gr}(P_0)=\textsf{gr}(Q^{\prime }_1)$
. The edge after
$P_0$
is always positive since it corresponds to
$\Lambda _0$
. Thus,
$$ \begin{align} \textsf{gr}(P_1)=\textsf{gr}(P_0)-1 \end{align} $$
and
$$ \begin{align} \textsf{gr}(Q_1)-\textsf{gr}(Q^{\prime}_1)=\kappa+1. \end{align} $$
When the edge before
$P_0$
is also positive,
$$ \begin{align*} \textsf{gr}(Q^{\prime}_1)-\textsf{gr}(P_0)&=\textsf{gr}(Q^{\prime}_1)-\textsf{gr}(Q_1)+ \textsf{gr}(Q_1)-\textsf{gr}(Q_0)+\textsf{gr}(Q_0)-\textsf{gr}(P_0)\\ &=(-\kappa-1)+(\textsf{gr}(P_1)-\textsf{gr}(P_0))+(\textsf{gr}(P_0)+\kappa)-\textsf{gr}(P_0)\\ &=\textsf{gr}(P_1)-\textsf{gr}(P_0)-1\\ &=0. \end{align*} $$
The second equality follows from (4.15), Lemma 4.7, and (4.12). The last equality follows from (4.14). Similarly, when the edge before
$P_0$
is negative,
$$ \begin{align*} \textsf{gr}(Q^{\prime}_1)-\textsf{gr}(P_0)&=\textsf{gr}(Q^{\prime}_1)- \textsf{gr}(Q_1)+\textsf{gr}(Q_1)-\textsf{gr}(Q_0)+\textsf{gr}(Q_0)-\textsf{gr}(P_0)\\ &=(-\kappa-1)+(\textsf{gr}(P_1)-\textsf{gr}(P_0)+\kappa)+ \textsf{gr}(P_0)-\textsf{gr}(P_0)\\ &=0.\\[-37pt] \end{align*} $$
Given an arbitrary relevant co-prime pair
$(p^*,q^*)$
and integers s and b, the expansion
$E(\overline {\Gamma }(p^*,q^*),s,b)$
may not be
$\overline {\Gamma }(p,q)$
for any co-prime
$(p,q)$
with q odd. Consider the pair
$(5,3)$
. Suppose
$E(\overline {\Gamma }(5,3),2,3)\cong \overline {\Gamma }(p,q)$
for some pair
$(p,q)$
. Define
$\kappa $
,
$\kappa '$
,
$\xi $
, and
$\xi '$
for
$(p,q)$
as in (4.2) and (4.3). Since the sizes of the segments of
$E(\overline {\Gamma }(5,3),2,3)$
are either 2 or 3 and the blocks have length 3 or 2,
$\kappa $
must be 2, and
$\kappa '$
must be 3. By Proposition 4.9,
$\overline {\Gamma }(5,3)\cong R(\overline {\Gamma })(p,q)$
. By Lemma 4.5,
$q^*=3$
is equal to
$\xi $
or
$\xi '-\xi $
. Since
$\xi '-\xi $
cannot be positive,
$\xi =3$
. Also, by Proposition 4.5,
$p\,\textsf{mod}\, q=\xi =5$
. Thus,
$q=3(5)+3=18$
, which is not odd.
5 Proof of Lemma 3.5
In this section, we reinterpret Lemma 3.5 as a set of properties of the cycle graph
$\overline {\Gamma }(p,q)$
. These properties will hold for simple relevant co-prime pairs
$(p,q)$
with
$q=1$
or
$(p\,\textsf{mod}\, q)=1$
. Then, it is shown that these conditions hold for any relevant co-prime pair of integers p and q with p positive and q odd by a strong induction argument using the relative isomorphism between
$\overline {\Gamma }(p,q)$
and
$\overline {\Gamma }(p,-q)$
and the reduction from
$\overline {\Gamma }(p,q)$
to
$R(\overline {\Gamma })(p,q)$
.
5.1 Making words from graphs
Given an incremental path
$\Gamma $
, a word
$\rho (\Gamma )$
in
$\mathcal{S}$
can be defined as follows: Let
$\{P_1,\ldots ,P_n\}$
be the vertices of
$\Gamma $
indexed so that the edge
$(P_i,P_{i+1})$
is in
$\Gamma $
. For
$i=2,\ldots ,n$
, let
$s_i=\textsf{gr}(P_i)-\textsf{gr}(P_{i-1})$
and let
$N_i=\textsf{gr}(Q_i)+\theta (s_i)$
where
$\theta (1)=1$
and
$\theta (-1)=0$
. Define
$$ \begin{align} \rho(\Gamma):=\left\{\begin{array}{ll} S_{N_3}^{s_3}S_{N_5}^{s_5}\cdots S_{N_k}^{s_k},&\text{if }n>2\text{ and }\textsf{gr}(P_1)\text{ is even,}\\ S_{N_2}^{s_2}S_{N_4}^{s_4}\cdots S_{N_k}^{s_k},&\text{if }n>1\text{ and }\textsf{gr}(P_1)\text{ is odd,}\\ 1,&\text{otherwise,} \end{array} \right. \end{align} $$
where
$k=n-1$
, if
$n\equiv \textsf{gr}(P_1)$
modulo 2, and
$k=n$
, if
$n\not \equiv \textsf{gr}(P_1)$
modulo 2. Given a two-bridge link
$L(p/q)$
, by Proposition 3.2,
$\rho (\Gamma (p,q))$
is the word
$R_0$
.
Lemma 5.1 Given incremental paths
$\Gamma $
and
$\Gamma '$
such that the last vertex of
$\Gamma $
has the same grading as the first vertex of
$\Gamma '$
,
$$\begin{align*}\rho(\Gamma*\Gamma')=\rho(\Gamma)\rho(\Gamma'). \end{align*}$$
Proof Let
$\{P_1,\ldots ,P_n\}$
and
$\{P_1',\ldots ,P^{\prime }_{n'}\}$
be the vertex sets for incremental paths
$\Gamma $
and
$\Gamma '$
, respectively. Also, define
$N_2,\ldots ,N_n$
and
$s_2,\ldots ,s_n$
for
$\Gamma $
as in the definition of
$\rho $
. Similarly, define
$N_2',\ldots ,N^{\prime }_{n'}$
and
$s_2',\ldots ,s^{\prime }_{n'}$
for
$\Gamma '$
. Let
$\Gamma ''=\Gamma *\Gamma '$
, which has length
$n+n'-1$
, and define
$N_2'',\ldots ,N^{\prime \prime }_{n+n'-1}$
and
$s_2'',\ldots ,s^{\prime \prime }_{n+n'-1}$
for
$\Gamma ''$
as the analogous integers are defined for
$\Gamma $
and
$\Gamma '$
.
This result is just a matter of computing
$\rho (\Gamma *\Gamma ')$
for each case of (5.1) for
$\Gamma $
and
$\Gamma '$
. For example, suppose
$\textsf{gr}(P_1)$
and n are even,
$n>2$
, and
$n'>1$
. Then, since n is even,
$$\begin{align*}\textsf{gr}(P^{\prime}_1)=\textsf{gr}(P_n)\equiv(\textsf{gr}(P_1)+n-1)\equiv\textsf{gr}(P_1)+1,\hspace{0.7cm}(\textsf{mod}\;2) \end{align*}$$
so since
$\textsf{gr}(P_1)$
is even,
$\textsf{gr}(P^{\prime }_1)$
is odd. Thus,
$$\begin{align*}\rho(\Gamma)=S_{N_3}^{s_3}S_{N_5}^{s_5}\cdots S_{N_{n-1}}^{s_{n-1}} \end{align*}$$
and
$$\begin{align*}\rho(\Gamma')=S_{N_2}^{s_2}S_{N_4}^{s_4}\cdots S_{N_k}^{s_k}, \end{align*}$$
where
$k=n'$
when
$n'$
is even and
$k=n'-1$
when
$n'$
is odd.
For each
$i=1,\ldots ,n+n'-1$
,
$$\begin{align*}\textsf{gr}(P^{\prime\prime}_i)=\left\{ \begin{array}{ll} \textsf{gr}(P_i),&\text{when }1\leq i\leq n,\\ \textsf{gr}(P^{\prime}_{i-n+1}),&\text{when }n\leq i\leq n+n'-1. \end{array} \right. \end{align*}$$
Thus, when
$2\leq i\leq n$
,
$s^{\prime \prime }_i=s_i$
, and
$N^{\prime \prime }_i=N_i$
, and when
$n+1\leq i\leq n+n'-1$
,
$s^{\prime \prime }_i=s_{i-n+1}$
, and
$N^{\prime \prime }_i=N_{i-n+1}$
. Therefore,
$$\begin{align*}\rho(\Gamma*\Gamma')=S_{N_3}^{s_3}S_{N_5}^{s_5}\cdots S_{N_{n-1}}^{s_{n-1}}S_{N_2'}^{s_2'}S_{N_4'}^{s_4'}\cdots S_{N^{\prime}_{k}}^{s^{\prime}_{k}}=\rho(\Gamma)\rho(\Gamma'). \end{align*}$$
The proofs of all the other cases are similar.
Lemma 5.2 Given two closable incremental paths
$\Gamma $
and
$\Gamma '$
such that
$\textsf{cl}(\Gamma )$
is isomorphic to
$\textsf{cl}(\Gamma ')$
, then
$\rho (\Gamma )$
and
$\rho (\Gamma ')$
are cyclic permutations of each other.
Proof Since
$\Gamma $
and
$\Gamma '$
have isomorphic closures, they must have the same number of vertices. Let
$\{P_0,\ldots ,P_n\}$
and
$\{P^{\prime }_0,\ldots ,P^{\prime }_n\}$
be the vertices in order of
$\Gamma $
and
$\Gamma '$
, respectively. Let
$\{Q_0,\ldots ,Q_{n-1}\}$
be the vertex set of
$\textsf{cl}(\Gamma )$
chosen such that
$\textsf{gr}(Q_i)=\textsf{gr}(P_i)$
for
$i=0,\ldots ,n-1$
. Likewise, let
$\{Q^{\prime }_0,\ldots ,Q^{\prime }_{n-1}\}$
be the vertex set of
$\textsf{cl}(\Gamma ')$
chosen such that
$\textsf{gr}(Q^{\prime }_i)=\textsf{gr}(P^{\prime }_i)$
for
$i=0,\ldots ,n-1$
.
Since
$\textsf{cl}(\Gamma )\cong \textsf{cl}(\Gamma ')$
, there is a directed graph isomorphism from
$f:\textsf{cl}(\Gamma )\cong \textsf{cl}(\Gamma ')$
, which preserves gradings. Let k be the index of the vertex in
$\textsf{cl}(\Gamma )$
such that
$f(Q_k)=Q^{\prime }_0$
. If
$k=0$
, then f maps
$Q_i$
to
$Q^{\prime }_i$
for each
$i=0,\ldots ,n-1$
. It follows that
$\textsf{gr}(P_i)=\textsf{gr}(P^{\prime }_i)$
for each
$i=0,\ldots ,n$
so
$\rho (\Gamma )=\rho (\Gamma ')$
.
Suppose
$k\neq 0$
. Let
$\Upsilon $
be the subgraph of
$\Gamma $
induced by
$P_0,\ldots ,P_k$
, and let
$\Omega $
be the subgraph of
$\Gamma $
induced by
$P_k,\ldots ,P_n$
. Since
$f(Q_0)=Q^{\prime }_{n-k}$
and
$f(Q_k)=Q^{\prime }_0$
, the subgraph of
$\Gamma '$
induced by
$P^{\prime }_{n-k},\ldots ,P^{\prime }_n$
must be isomorphic to
$\Upsilon $
, and the subgraph of
$\Gamma '$
induced by
$P^{\prime }_0,\ldots ,P^{\prime }_{n-k}$
must be isomorphic to
$\Omega $
. Thus,
$\Gamma \cong \Upsilon *\Omega $
and
$\Gamma '\cong \Omega *\Upsilon $
(see Figure 11 for example). Therefore,
$\rho (\Gamma )=\rho (\Upsilon )\rho (\Omega )$
and
$\rho (\Gamma ')=\rho (\Omega )\rho (\Upsilon )$
.
Figure 11: Closable graphs
$\Gamma $
and
$\Gamma '$
with isomorphic closures with the subgraphs
$\Upsilon $
(dashed) and
$\Omega $
(dotted) shown.
5.2 Summits and bottoms in cycle graphs
Let
$(p,q)$
be a relevant co-prime pair, and define M and m for
$L(p/q)$
as in Section 3. Our goal is to prove Lemma 3.5. By Proposition 3.2
(d), it is sufficient to show Lemma 3.5 for the relator
$R_0$
. Thus, we are interested in the appearances of
$S^{\delta }_M$
and
$S^{\delta }_m$
in the word
$R_0$
. When M is odd, the ith S-generator of
$R_0$
is
$S^{\delta }_M$
precisely when
$\sigma _{2i}=M+1$
, and when M is even, the ith S-generator of
$R_0$
is
$S^{\delta }_M$
when
$\sigma _{2i-1}=M+1$
. Thus, appearances of
$S^{\delta }_M$
in
$R_0$
correspond to the indices when
$\sigma _i$
is maximal. Similarly, the ith S-generator of
$R_0$
is
$S^{\delta }_m$
precisely when
$\sigma _{2i-1}=m$
when m is odd or
$\sigma _{2i}=m$
when m is even. Thus, appearances
$S^{\delta }_m$
in
$R_0$
correspond to the indices when
$\sigma _i$
is minimal.
A vertex, P, in a graded graph
$\Gamma $
is called a summit if
$\textsf{gr}(P)\geq \textsf{gr}(Q)$
for any vertex Q in
$\Gamma $
. Similarly, P is called a bottom if
$\textsf{gr}(P)\leq \textsf{gr}(Q)$
for any vertex Q in
$\Gamma $
. For each relevant co-prime pair
$(p,q)$
, the grading of a summit of
$\Gamma (p,q)$
is always
$M+1$
and the grading of a bottom of
$\Gamma (p,q)$
is always m. Furthermore, the appearances of
$S_M$
in
$R_0$
correspond precisely to the summits in
$\Gamma (p,q)$
, and the appearances of
$S_m$
correspond to bottoms.
5.3 Symmetric incremental paths and cycles
It is useful to know when an incremental cycle is relatively isomorphic to itself after rotating
$180^{\circ }$
and reversing its edges. More precisely, we call an incremental cycle
$\Gamma $
symmetric if there is a bijection
$\phi :V(\Gamma )\to V(\Gamma )$
such that:
-
(1)
$(P,Q)$
is an edge of
$\Gamma $
if and only if
$(\phi (Q),\phi (P))$
is an edge of
$\Gamma $
for any two vertices P and Q in
$\Gamma $
and -
(2) for some integer k,
$\textsf{gr}(P)+\textsf{gr}(\phi (P))=k$
for every vertex P in
$\Gamma $
.
An incremental path
$\Gamma $
is called symmetric if
$\textsf{cl}(\Gamma )$
is symmetric (see Figure 12). The symmetry of incremental paths and cycles plays an important role in investigating properties (M5) and (m5) of Lemma 3.5.
Figure 12: A symmetric incremental cycle. The first and last vertices are identified.
$\phi $
is the unique order-reversing bijection defined by
$\phi (P_1)=P_{10}$
.
5.4 Reinterpretation of Lemma 3.5
Here, we reinterpret Lemma 3.5 in terms of incremental paths and cycles. Given a closable incremental path
$\Gamma $
and a positive integer n, define
$\Gamma ^n$
to be the concatenation of n copies of
$\Gamma $
. We call a relevant co-prime pair
$(p,q)$
an pre-RTFN pair if for some incremental path
$\Gamma $
whose closure is isomorphic to
$\overline {\Gamma }(p,q)$
, there are a positive integer N, sequences of subgraphs of
$\Gamma $
,
$$\begin{align*}\Gamma_0,\ldots,\Gamma_N, \end{align*}$$
$$\begin{align*}\Upsilon_1,\ldots,\Upsilon_N, \end{align*}$$
and
$$\begin{align*}\Omega_1,\ldots,\Omega_N, \end{align*}$$
and a sequence of positive integers
$$\begin{align*}n_1,\ldots,n_N \end{align*}$$
such that the following conditions are satisfied:
-
(R1)
$\Gamma _0=\Gamma $
. -
(R2)
$\Gamma _N$
is isomorphic to the graph
$\Gamma _{\textsf{top}}$
defined in Figure 13.Figure 13: The graph
$\Gamma _{\textsf{top}}$
. -
(R3) For each
$i=1,\ldots ,N$
,
$$\begin{align*}\Gamma_{i-1}\cong\Upsilon_i*\Gamma_i^{n_i}*\Omega_i. \end{align*}$$
-
(R4) For each
$i=1,\ldots ,N$
, no summits of
$\textsf{cl}(\Gamma )$
appear in
$\Upsilon _i$
or
$\Omega _i$
. -
(R5) For each
$i=0,\ldots ,N$
,
$\Gamma _i$
is symmetric, and when
$i\geq 1$
,
$\Gamma _i$
contains no bottoms of
$\textsf{cl}(\Gamma )$
.
For example, Figure 14 demonstrates that
$(33,23)$
is a pre-RTFN pair.
Figure 14:
$(33,23)$
is a pre-RTFN pair.
Lemma 5.3
$(p,q)$
is a pre-RTFN pair if and only if
$(p,-q)$
is a pre-RTFN pair.
Proof By Proposition 4.2,
$\Gamma (p,q)$
and
$\Gamma (p,-q)$
have relatively isomorphic closures, so the conclusion of the lemma follows immediately.
Lemma 5.4 Suppose
$(p,q)$
is a relevant co-prime pair. If
$(p,q)$
is a pre-RTFN pair, then
$L(p/q)$
satisfies Lemma 3.5.
Proof By Proposition 3.2
(d), it is sufficient to show that Lemma 3.5 holds for
$R_0$
. Let
$(p,q)$
be a pre-RTFN pair. Then, we have a graph
$\Gamma $
whose closure is isomorphic to
$\overline {\Gamma }(p,q)$
satisfying (R1)–(R5).
For each
$i=0,\ldots , N$
, define
$$\begin{align*}\widehat{A}_i:=\rho(\Gamma_{i}), \end{align*}$$
and when
$i>0$
, define
$$\begin{align*}\widehat{V}_i:=\rho(\Omega_{i})\rho(\Upsilon_{i}) \text{ and } \widehat{W}_i:=\rho(\Upsilon_{i}). \end{align*}$$
Proof of (M1) and (M2)
By (R1),
$\textsf{cl}(\Gamma _0)$
is isomorphic to
$\overline {\Gamma }(p,q)$
. Therefore, by Lemma 5.2,
$\widehat {A}_0=\rho (\Gamma _0)$
is a cyclic permutation of
$\rho (\Gamma (p,q))$
which is
$R_0$
.
By (R2),
$$\begin{align*}A_N=\rho(\Gamma_N)=S^{\delta}_M. \end{align*}$$
Proof of (M3)
Suppose i is an integer with
$1\leq i\leq N$
. By (R3),
$$\begin{align*}\Gamma_{i-1}\cong\Upsilon_i*\Gamma_i^{n_i}*\Omega_i. \end{align*}$$
Therefore,
$$ \begin{align*} \widehat{A}_{i-1}&=\rho(\Gamma_{i-1})\\ &=\rho(\Upsilon_i*\Gamma_i^{n_i}*\Omega_i)\\ &=\rho(\Upsilon_i)\rho(\Gamma_i)^{n_i}\rho(\Omega_i)\\ &=\rho(\Upsilon_i)\rho(\Gamma_i)^{n_i}\rho(\Omega_i)\rho(\Upsilon_i)\rho(\Upsilon_i)^{-1}\\ &=\widehat{W}_i\widehat{A}_i^{n_i}\widehat{V}_i\widehat{W}_i^{-1}, \end{align*} $$
so
$$\begin{align*}\widehat{W}_i^{-1}\widehat{A}_{i-1}\widehat{W}_i=\widehat{A}_i^{n_i}\widehat{V}_i.\\[-35pt] \end{align*}$$
Proof of (M4)
For each vertex P in
$\Gamma (p,q)$
,
$m\leq P \leq M+1$
. Thus, since for each
$i=1,\ldots ,N$
,
$\widehat {W}_i$
and
$\widehat {V}_i$
are subgraphs of
$\Gamma (p,q)$
,
$\rho (\widehat {W}_i)$
and
$\rho (\widehat {V}_i)$
are contained in the subgroup generated by
$\{S_m,\ldots ,S_M\}$
. Since no summits of
$\Gamma $
appear in
$\Upsilon _i$
or
$\Omega _i$
,
$S^{\delta }_M$
cannot appear in
$\widehat {V}_i$
or
$\widehat {W}_i$
.
Proof of (M5)
Suppose i is an integer with
$0\leq i\leq N$
. The maximum grading of a vertex in
$\Gamma _i$
is
$M+1$
. Let l be the minimum grading of a vertex in
$\Gamma _i$
. For some integer coefficients
$b_l,b_{l+1}\ldots ,b_M$
,
$$\begin{align*}[\rho(\Gamma_i)]=b_lS^{\prime}_l+b_{l+1}S^{\prime}_{l+1}+\cdots+b_MS^{\prime}_M. \end{align*}$$
Our goal is to show that for each
$j=0,\ldots ,M-l$
,
$|b_{l+j}|=|b_{M-j}|$
.
The vertices of
$\textsf{cl}(\Gamma _i)$
can be classified into four types according to Figure 15. Define
$v_{(**)}(n)$
to be the number vertices in
$\textsf{cl}(\Gamma _i)$
of type
$(**)$
with grading n.
Figure 15: The four vertex types.
Suppose
$n=l,\ldots , M$
. When n is even,
$S_n$
always has exponent
$-1$
in
$\rho (\Gamma _i)$
, and
$S^{-1}_n$
appears precisely when there is negative edge followed by a vertex in
$\textsf{cl}(\Gamma _i)$
with grading n, so
$$ \begin{align} |b_{n}|=v_{(--)}(n)+v_{(-+)}(n). \end{align} $$
Similarly, when n is odd,
$S_n$
always has exponent
$1$
in
$\rho (\Gamma _i)$
, and
$S_n$
appears precisely when there is a vertex in
$\textsf{cl}(\Gamma _i)$
with grading n followed by a positive edge, so
$$ \begin{align} |b_{n}|=v_{(++)}(n+1)+v_{(+-)}(n+1). \end{align} $$
Since
$\Gamma _i$
is symmetric by (R5), there is an order-reversing bijection
$\phi $
of the vertex set of
$\textsf{cl}(\Gamma _i)$
such that
$\textsf{gr}(P)+\textsf{gr}(\phi (P))=l+M+1$
for each vertex P in
$\textsf{cl}(\Gamma _i)$
. Furthermore, P and
$\phi (P)$
have types rotated
$180^{\circ }$
with arrows reversed (see Figure 16). As a consequence,
$$ \begin{align} \begin{aligned} v_{(--)}(n)=v_{(--)}(l+M+1-n),\\ v_{(-+)}(n)=v_{(+-)}(l+M+1-n),\\ v_{(++)}(n)=v_{(++)}(l+M+1-n),\\ v_{(+-)}(n)=v_{(-+)}(l+M+1-n). \end{aligned} \end{align} $$
Each positive edge connects a vertex of type
$(*+)$
to a vertex of type
$(+*)$
. Likewise, each negative edge connects a vertex of type
$(*-)$
to a vertex of type
$(-*)$
(see Figure 17). Thus,
$$ \begin{align} \begin{aligned} v_{(++)}(n)+v_{(-+)}(n)=v_{(++)}(n+1)+v_{(+-)}(n+1),\\ v_{(--)}(n)+v_{(+-)}(n)=v_{(--)}(n-1)+v_{(-+)}(n-1). \end{aligned} \end{align} $$
The incremental path
$\Gamma _i$
is closable, and the gradings of adjacent vertices in
$\Gamma _i$
differ by
$\pm 1$
. It follows that every time
$\Gamma _i$
passes from below to above some grading level at a vertex,
$\Gamma _i$
must pass from above to below the same grading level at some other vertex. Thus, in each grading n,
$$ \begin{align} v_{(++)}(n)=v_{(--)}(n). \end{align} $$
Figure 16: The effect of
$\phi $
on vertex type.
Figure 17: Vertex types of adjacent vertices.
Now, we show that
$|b_{l+j}|=|b_{M-j}|$
. Let j be an integer such that
$0\leq j \leq M-l$
. When
$l+j$
and
$M-j$
are both even,
$$ \begin{align*} |b_{l+j}|&=v_{(--)}(l+j)+v_{(-+)}(l+j)\\ &=v_{(--)}(M-j+1)+v_{(+-)}(M-j+1)\\ &=v_{(--)}(M-j)+v_{(-+)}(M-j)\\ &=|b_{M-j}| \end{align*} $$
When
$l+j$
and
$M-j$
are odd,
$$ \begin{align*} |b_{l+j}|&=v_{(++)}(l+j+1)+v_{(+-)}(l+j+1)\\ &=v_{(++)}(M-j)+v_{(-+)}(M-j)\\ &=v_{(++)}(M-j+1)+v_{(+-)}(M-j+1)\\ &=|b_{M-j}| \end{align*} $$
When
$l+j$
is even and
$M-j$
is odd,
$$ \begin{align*} |b_{l+j}|&=v_{(--)}(l+j)+v_{(-+)}(l+j)\\ &=v_{(--)}(M-j+1)+v_{(+-)}(M-j+1)\\ &=v_{(++)}(M-j+1)+v_{(+-)}(M-j+1)\\ &=|b_{M-j}| \end{align*} $$
by (5.2), (5.4), (5.6), and (5.3).
When
$l+j$
is odd and
$M-j$
is even,
$$ \begin{align*} |b_{l+j}|&=v_{(++)}(l+j+1)+v_{(+-)}(l+j+1)\\ &=v_{(++)}(M-j)+v_{(-+)}(M-j)\\ &=v_{(--)}(M-j)+v_{(-+)}(M-j)\\ &=|b_{M-j}| \end{align*} $$
by (5.3), (5.4), (5.6), and (5.2).
When
$i\geq 1$
, no bottoms appear in
$\Gamma _i$
, so
$l>m$
.
Proof of (m1)–(m5)
Since
$\Gamma _0=\Gamma $
is symmetric, there is an order-reversing bijection
$\overline {\phi }$
on the vertices of
$\textsf{cl}(\Gamma )$
such that
$$\begin{align*}\textsf{gr}(P)+\textsf{gr}(\overline{\phi}(P))=m+M+1 \end{align*}$$
for each vertex P in
$\textsf{cl}(\Gamma )$
. Thus,
$\overline {\phi }$
induces a map on the subgraphs of
$\textsf{cl}(\Gamma )$
.
For each
$i=0,\ldots , N$
, define
and when
$i>0$
, define
(m1)–(m5) follow from proofs similar to the those used for (M1)–(M5).
5.5 Using reductions for induction
Suppose
$(p,q)$
is a relevant co-prime pair with
$q>1$
and with
$(p\,\textsf{mod}\, q)\neq 1$
. By Lemma 4.5,
$R(\overline {\Gamma })(p,q)$
is isomorphic to
$\overline {\Gamma }(p^*,q^*)$
for some relevant co-prime pair
$(p^*,q^*)$
defined as in Lemma 4.5. Along with Lemma 5.3,
$\overline {\Gamma }(p,q)$
can be simplified through a sequence of reductions and relative isomorphisms to
$\overline {\Gamma }(p_0,q_0)$
such that
$q_0=1$
or
$(p\,\textsf{mod}\, q)=1$
.
Example 5.5
$$\begin{align*}\overline{\Gamma}(119,43)\overset{R}{\rightarrow}\overline{\Gamma}(33,-23)\overset{rel.}{\cong} \overline{\Gamma}(33,23)\overset{R}{\rightarrow}\overline{\Gamma}(10,3). \end{align*}$$
The goal now is to show that when
$(p^*,q^*)$
is a pre-RTFN pair,
$(p,q)$
is also a pre-RTFN pair.
5.6 Leading and trailing vertices
Call a vertex in
$\overline {\Gamma }(p,q)$
at the end of a
$(\kappa +1)$
-segment a leading vertex, and a vertex at the beginning of a
$(\kappa +1)$
-segment a trailing vertex (see Figure 18). Let P be a leading vertex in
$\overline {\Gamma }(p,q)$
, and let
$\Lambda _L$
be the
$(\kappa +1)$
-segment of
$\overline {\Gamma }(p,q)$
immediately preceding P. Define
$f_L(P)$
to be the vertex at the end of the edge in
$R(\overline {\Gamma })(p,q)$
corresponding to
$\Lambda _L$
. Let P be a trailing vertex in
$\overline {\Gamma }(p,q)$
, and let
$\Lambda _T$
be the
$(\kappa +1)$
-segment of
$\overline {\Gamma }(p,q)$
immediately following P. Define
$f_T(P)$
to be the vertex at the beginning of the edge in
$R(\overline {\Gamma })(p,q)$
corresponding to
$\Lambda _T$
. When the path from a leading vertex
$P_A$
to a trailing vertex
$P_B$
is a
$\kappa $
-block,
$f_L(P_A)=f_T(P_B)$
.
Figure 18:
$P_A$
is a leading vertex of
$\overline {\Gamma }(13,11)$
, and
$P_B$
is a trailing vertex of
$\overline {\Gamma }(13,11)$
(left).
$f_L(P_A)=f_T(P_B)=P^*$
in
$R(\overline {\Gamma })(13,11)$
(right).
$f_L$
is a bijection from the leading vertices of
$\Gamma (p,q)$
to the vertex set of
$R(\overline {\Gamma })(p,q)$
, and
$f_T$
is a bijection from the trailing vertices of
$\Gamma (p,q)$
to the vertex set of
$R(\overline {\Gamma })(p,q)$
. Let
$P^*$
be a vertex in
$R(\overline {\Gamma })(p,q)$
. Since
$f_L^{-1}(P^*)$
and
$f_T^{-1}(P^*)$
are separated by a
$\kappa $
-block of length
$\kappa '$
or
$\kappa '-1$
, the gradings of
$f_L^{-1}(P^*)$
and
$f_T^{-1}(P^*)$
are either the same of differ by
$\pm \kappa $
.
Any vertex in
$\overline {\Gamma }(p,q)$
at the end of a positive (or negative) segment is called a peak (resp. valley). There is a relationship between the gradings of the vertices in
$\overline {\Gamma }(p,q)$
and
$R(\overline {\Gamma })(p,q)$
.
Proposition 5.6 Let P and Q be leading vertices of
$\overline {\Gamma }(p,q)$
.
-
(1) If P and Q are both peaks or both valleys, then
$$\begin{align*}\textsf{gr}(f_L(P))-\textsf{gr}(f_L(Q))=\textsf{gr}(P)-\textsf{gr}(Q). \end{align*}$$
-
(2) If P is a valley and Q is a peak, then
$$\begin{align*}\textsf{gr}(f_L(P))-\textsf{gr}(f_L(Q))=\textsf{gr}(P)-\textsf{gr}(Q)-\kappa. \end{align*}$$
-
(3) If P is a peak and Q is a valley, then
$$\begin{align*}\textsf{gr}(f_L(P))-\textsf{gr}(f_L(Q))=\textsf{gr}(P)-\textsf{gr}(Q)+\kappa. \end{align*}$$
Proof This follows from Lemma 4.7. Let
$\Gamma ^*$
be the unique path subgraph of
$R(\overline {\Gamma })(p,q)$
beginning with
$f_L(P)$
and ending
$f_L(Q)$
. Let e be the sign of the edge in
$R(\overline {\Gamma })(p,q)$
preceding
$f_L(P)$
. Let
$\Gamma $
be
$\tilde {E}(\Gamma ^*,\kappa ,\kappa ',e)$
. Finally, let
$Q_0$
be the first vertex in
$\Gamma $
.
The vertices P and Q are at the end of
$(\kappa +1)$
-segments, which we will denote as
$\Lambda _P$
and
$\Lambda _Q$
, respectively. The first vertex in
$\Gamma ^*$
is
$f_L(P)$
. Also, e and
$\Lambda _P$
will always have the same sign. Therefore,
$$\begin{align*}\textsf{gr}(P)-\textsf{gr}(Q_0)=0. \end{align*}$$
Thus,
$$ \begin{align} \begin{aligned} \textsf{gr}(P)-\textsf{gr}(Q)&=(\textsf{gr}(P)-\textsf{gr}(Q_0))-(\textsf{gr}(Q)-\textsf{gr}(Q_0))\\ &=\textsf{gr}(Q_0)-\textsf{gr}(Q). \end{aligned} \end{align} $$
Also, the first vertex
$P_0$
in
$\Gamma ^*$
is
$f_L(P)$
, so
$$ \begin{align} \textsf{gr}(P_0)-\textsf{gr}(f_L(Q))=\textsf{gr}(f_L(P))-\textsf{gr}(f_L(Q)). \end{align} $$
The signs of e are determined by whether P is a peak or a valley:
$$\begin{align*}e= \begin{cases} 1, & P\text{ is a peak,}\\ -1, & P\text{ is a valley.} \end{cases} \end{align*}$$
Also,
$\Lambda _Q$
is positive when Q is a peak and negative when Q is a valley. The desired result follows from Lemma 4.7, (5.7), and (5.8).
Corollary 5.7 Given a leading vertex P of
$\overline {\Gamma }(p,q)$
, P is a summit of
$\overline {\Gamma }(p,q)$
if and only if
$f_L(P)$
is a summit of
$R(\overline {\Gamma })(p,q)$
.
Proof Suppose a leading vertex P of
$\overline {\Gamma }(p,q)$
is a summit. Consider a vertex in
$R(\overline {\Gamma })(p,q)$
which is
$f_L(Q)$
for some leading vertex Q of
$\overline {\Gamma }(p,q)$
. Since P is a summit,
$\textsf{gr}(P)-\textsf{gr}(Q)\geq 0$
. Since P is a peak, by Proposition 5.6, either
$$\begin{align*}\textsf{gr}(f_L(P))-\textsf{gr}(f_L(Q))=\textsf{gr}(P)-\textsf{gr}(Q)\geq 0 \end{align*}$$
or
$$\begin{align*}\textsf{gr}(f_L(P))-\textsf{gr}(f_L(Q))=\textsf{gr}(P)-\textsf{gr}(Q)+\kappa\geq 0. \end{align*}$$
Thus,
$f_L(P)$
is a summit of
$R(\overline {\Gamma })(p,q)$
.
Conversely, suppose for some leading vertex P of
$\overline {\Gamma }(p,q)$
that
$f_L(P)$
is a summit of
$R(\overline {\Gamma })(p,q)$
. Let Q be a summit of
$\overline {\Gamma }(p,q)$
, so
$\textsf{gr}(P)-\textsf{gr}(Q)\leq 0$
. Since Q is a peak, by Proposition 5.6,
$$\begin{align*}\textsf{gr}(P)-\textsf{gr}(Q)\geq\textsf{gr}(f_L(P))-\textsf{gr}(f_L(Q))\geq 0. \end{align*}$$
The last inequality is true since
$f_L(P)$
is a summit. Thus,
$\textsf{gr}(P)=\textsf{gr}(Q)$
, so since Q is a summit of
$\overline {\Gamma }(p,q)$
, P is also.
5.7 Proof of Lemma 3.5
We now have everything we need to show that every relevant co-prime pair
$(p,q)$
with p positive and q odd is a pre-RTFN pair. For each relevant co-prime pair, we need to find a positive integer N, sequences of subgraphs of
$\Gamma (p,q)$
$$\begin{align*}\Gamma_0,\ldots,\Gamma_N, \end{align*}$$
$$\begin{align*}\Upsilon_1,\ldots,\Upsilon_N, \end{align*}$$
and
$$\begin{align*}\Omega_1,\ldots,\Omega_N, \end{align*}$$
and integers
$$\begin{align*}n_1,\ldots,n_N, \end{align*}$$
satisfying (R1)–(R5). We prove this using a strong induction starting with the base cases below.
Let
$\Gamma $
be an incremental path, and let
$P,P'$
be vertices in
$\Gamma $
. Define
$\omega (\Gamma ,P',P)$
, the unique path in
$\textsf{cl}(\Gamma )$
from
$P'$
to P.
Lemma 5.8 Let
$(p,q)$
be a relevant co-prime pair with p and q positive and q odd. If
$q=1$
or
$(p\,\textsf{mod}\, q)=1$
, then
$(p,q)$
is a pre-RTFN pair.
Proof
$\Gamma (p,q)$
has
$2p+1$
vertices
$P_0\ldots ,P_{2p}$
.
When
$q=1$
, the grading are
$$\begin{align*}\textsf{gr}(P_i)= \begin{cases} i, & 0\leq i \leq p,\\ 2p-i, & p\leq i \leq 2p. \end{cases} \end{align*}$$
See Figure 19a.
Figure 19: Cycle graphs with
$q=1$
and
$(p\,\mathsf{mod}\, q)=1$
.
Make the following choices of subgraphs and integers:
-
• Let
$N=1$
. -
• Let
$\Gamma _0=\Gamma (p,q)$
. -
• Let
$\Gamma _1=\Gamma _{\textsf{top}}$
. -
• Let
$n_1=1$
. -
• Let
$\Upsilon _1=\omega (\Gamma (p,q),P_0,P_{p-1})$
. -
• Let
$\Omega _1=\omega (\Gamma (p,q),P_{p+1},P_{2p})$
.
It is clear that (R1) and (R2) are satisfied.
$$ \begin{align*} \Gamma_0=\Gamma(p,q)&=\omega(\Gamma(p,q),P_0,P_{\kappa})*\omega(\Gamma(p,q),P_{\kappa},P_{\kappa+2})*\omega(\Gamma(p,q),P_{\kappa+2},P_{2p})\\ &=\Upsilon_1*\omega(\Gamma(p,q),P_{\kappa},P_{\kappa+2})*\Omega_1\\ &=\Upsilon_1*\Gamma_1*\Omega_1. \end{align*} $$
Thus, (R3) is satisfied.
The grading of a summit of
$\Gamma (p,1)$
is p. Since the maximum grading of a vertices in
$\Upsilon _1$
or
$\Omega _1$
is
$p-1$
,
$\Upsilon _1$
or
$\Omega _1$
contain no summits of
$\Gamma (p,1)$
, so (R4) is satisfied.
Consider the map
$\phi :\overline {\Gamma }(p,1)\to \overline {\Gamma }(p,1)$
defined by
$$\begin{align*}\phi(P_i):= \begin{cases} P_{p-i}, & 0\leq i \leq p,\\ P_{3p-i}, & p < i <2p, \end{cases} \end{align*}$$
When
$0\leq i \leq p$
,
$$\begin{align*}\textsf{gr}(P_i)+\textsf{gr}(\phi(P_i))=i+p-i=p. \end{align*}$$
When
$p< i < 2p$
,
$$\begin{align*}\textsf{gr}(P_i)+\textsf{gr}(\phi(P_i))=2p-i+2p-(3p-i)=p, \end{align*}$$
so
$\Gamma _0$
is symmetric.
Since
$\Gamma _1\cong \Gamma _{\textsf{top}}$
, its closure has two vertices: one graded
$p-1$
and one graded p. Consider the map
$\phi :\textsf{cl}(\Gamma _1)\to \textsf{cl}(\Gamma _1)$
, which exchanges the two vertices. For each vertex P in
$\textsf{cl}(\Gamma _1)$
,
$$\begin{align*}\textsf{gr}(P)+\textsf{gr}(\phi(P))=p+p-1=2p-1, \end{align*}$$
so
$\Gamma _1$
is symmetric. Also, the minimum grading of a vertex in
$\Gamma (p,1)$
is 0, and the minimum grading of a vertex in
$\Gamma _1$
is p. Therefore, no bottoms of
$\Gamma (p,1)$
are in
$\Gamma _1$
. Thus, (R5) is satisfied.
When
$p\,\textsf{mod}\, q=1$
, define
$\kappa $
and
$\kappa '$
as in (4.2) and (4.3). Since
$p\,\textsf{mod}\, q=1$
,
$\kappa '=q$
, which is odd. By Proposition 4.3
(a) and (e),
$\overline {\Gamma }(p,q)$
has two
$(\kappa +1)$
-segments, and has
$2q-2 \ \kappa $
-segments. By Proposition 4.4
(a), the
$\kappa $
-segments must be contained in two
$\kappa $
-blocks of length
$q-1$
. It follows that
$\Gamma (p,q)$
is the concatenation of a positive
$(\kappa +1)$
-segment, a
$\kappa $
-block of length
$q-1$
, a negative
$(\kappa +1)$
-segment, followed by another
$\kappa $
-block of length
$q-1$
(see Figure 19b).
Explicitly, the gradings are
When
$\kappa =1$
, make the following choices:
-
• Let
$N=1$
. -
• Let
$\Gamma _0=\Gamma (p,q)$
. -
• Let
$\Gamma _1=\Gamma _{\textsf{top}}$
. -
• Let
$n_1=(q+1)/2$
. -
• Let
$\Upsilon _1=\omega (\Gamma (p,q),P_0,P_1)$
. -
• Let
$\Omega _1=\omega (\Gamma (p,q),P_{1+2n_1},P_{2p})$
.
When
$\kappa>1$
, make the following choices:
-
• Let
$N=2$
. -
• Let
$\Gamma _0=\Gamma (p,q)$
. -
• Let
$\Gamma _1=\omega (\Gamma (p,q),P_1,P_{1+2\kappa })$
. -
• Let
$\Gamma _2=\Gamma _{\textsf{top}}$
. -
• Let
$n_1=(q+1)/2$
. -
• Let
$n_2=1$
. -
• Let
$\Upsilon _1=\omega (\Gamma (p,q),P_0,P_1)$
. -
• Let
$\Omega _1=\omega (\Gamma (p,q),P_{1+2\kappa n_1},P_{2p})$
. -
• Let
$\Upsilon _2=\omega (\Gamma (p,q),P_1,P_{\kappa })$
. -
• Let
$\Omega _2=\omega (\Gamma (p,q),P_{\kappa +2},P_{2\kappa +1})$
.
Again, it is clear that (R1) and (R2) are satisfied.
When
$\kappa =1$
,
$$ \begin{align*} \Gamma_0=\Gamma(p,q)&=\omega(\Gamma(p,q),P_0,P_1)*\omega(\Gamma(p,q),P_1,P_{1+2n_1})*\omega(\Gamma(p,q),P_{1+2n_1},P_{2p})\\ &=\Upsilon_1*\Gamma_1^{n_1}*\Omega_1. \end{align*} $$
When
$\kappa>1$
,
$$ \begin{align*} \Gamma_0=\Gamma(p,q)&=\omega(\Gamma(p,q),P_0,P_1)*\omega(\Gamma(p,q),P_1,P_{1+2\kappa n_1})*\omega(\Gamma(p,q),P_{1+2\kappa n_1},P_{2p})\\ &=\Upsilon_1*\Gamma_1^{n_1}*\Omega_1 \end{align*} $$
and
$$ \begin{align*} \Gamma_1&=\omega(\Gamma(p,q),P_1,P_{1+2\kappa})\\ &=\omega(\Gamma(p,q),P_1,P_{\kappa})*\omega(\Gamma(p,q),P_{\kappa},P_{\kappa+2})*\omega(\Gamma(p,q),P_{\kappa+2},P_{2\kappa+1})\\ &=\Upsilon_2*\Gamma_2*\Omega_2. \end{align*} $$
Thus, (R3) is satisfied.
The grading of a summit of
$\Gamma (p,1)$
is
$\kappa +1$
. The maximum grading of a vertex in
$\Upsilon _1$
is 1, and the maximum grading of a vertex in
$\Upsilon _1$
,
$\Omega _1$
, or
$\Omega _2$
is
$\kappa $
. Thus,
$\Upsilon _1$
,
$\Upsilon _2$
,
$\Omega _1$
, or
$\Omega _2$
contains no summits of
$\Gamma (p,q)$
, so (R4) is satisfied.
Consider the map
$\phi :\overline {\Gamma }(p,q)\to \overline {\Gamma }(p,q)$
defined by
$$\begin{align*}\phi(P_i):= \begin{cases} P_{\kappa+1-i}, & 0 \leq i \leq \kappa+1,\\[-2pt] P_{2p+\kappa+1-i}, & \kappa+1 < i < 2p. \end{cases} \end{align*}$$
When
$0\leq i \leq \kappa +1$
,
$$\begin{align*}\textsf{gr}(P_i)+\textsf{gr}(\phi(P_i))=i+\kappa+1-i=\kappa+1. \end{align*}$$
When
$p\leq i \leq p+\kappa +1$
,
$$\begin{align*}p\leq 2p+\kappa+1-i \leq p+\kappa+1. \end{align*}$$
Thus,
$$\begin{align*}\textsf{gr}(P_i)+\textsf{gr}(\phi(P_i))=p+\kappa+1-i+p+\kappa+1-(2p+\kappa+1-i) =\kappa+1. \end{align*}$$
Let
$j\in \{2,4,\ldots ,q-1\}$
.
When
$(j-1)\kappa +1\leq i \leq j\kappa +1$
,
$$\begin{align*}2p+\kappa+1-(j\kappa+1)\leq 2p+\kappa+1-i \leq 2p+\kappa+1-((j-1)\kappa +1). \end{align*}$$
Since
$p=q\kappa +1$
, we can substitute
$2p=p+q\kappa +1$
on each side to obtain
$$\begin{align*}p+(q+1-j)\kappa+1\leq 2p+\kappa+1-i \leq p+(q+2-j)\kappa+1. \end{align*}$$
Let
$l=q+1-j$
. Thus,
$$\begin{align*}p+l\kappa+1\leq 2p+\kappa+1-i \leq p+(l+1)\kappa+1. \end{align*}$$
Therefore,
$$ \begin{align*} \textsf{gr}(P_i)+\textsf{gr}(\phi(P_i))&=j\kappa+2-i+p+(l+1)\kappa+1-(2p+\kappa+1-i)\\ &=(j+l)\kappa+2-p\\ &=q\kappa+1-p+\kappa+1\\ &=\kappa+1. \end{align*} $$
When
$j\kappa +1\leq i \leq (j+1)\kappa +1$
,
$$\begin{align*}2p+\kappa+1-((j+1)\kappa+1)\leq 2p+\kappa+1-i \leq 2p+\kappa+1-(j\kappa +1). \end{align*}$$
We substitute
$2p=p+q\kappa +1$
on each side to obtain
$$\begin{align*}p+(q-j)\kappa+1\leq 2p+\kappa+1-i \leq p+(q-j+1)\kappa+1. \end{align*}$$
Thus,
$$\begin{align*}p+(l-1)\kappa+1\leq 2p+\kappa+1-i \leq p+l\kappa+1. \end{align*}$$
Therefore,
$$ \begin{align*} \textsf{gr}(P_i)+\textsf{gr}(\phi(P_i))&=i-j\kappa+2p+\kappa+1-i-p-(l-1)\kappa-1\\ &=-(j+l)\kappa+p+\kappa+\kappa\\ &=-(q+1)\kappa+p+\kappa+\kappa\\ &=p-q\kappa+\kappa\\ &=\kappa+1. \end{align*} $$
When
$p+j\kappa +1\leq i \leq p+(j+1)\kappa +1$
, there is some integer c such that
$$\begin{align*}(j-1)\kappa +1\leq c \leq j\kappa+1 \end{align*}$$
and
$P_i=\phi (P_c)$
. Since
$\phi ^2$
is the identity map,
$$\begin{align*}\textsf{gr}(P_i)+\textsf{gr}(\phi(P_i))=\textsf{gr}(\phi(P_c))+\textsf{gr}(P_c)=\kappa+1. \end{align*}$$
When
$p+(j-1)\kappa +1\leq i \leq p+j\kappa +1$
, there is some integer c such that
$$\begin{align*}j\kappa +1\leq c \leq (j+1)\kappa+1 \end{align*}$$
and
$P_i=\phi (P_c)$
. Similar to the previous case,
$$\begin{align*}\textsf{gr}(P_i)+\textsf{gr}(\phi(P_i))=\textsf{gr}(\phi(P_c))+\textsf{gr}(P_c)=\kappa+1. \end{align*}$$
Therefore,
$\Gamma _0$
is symmetric.
The choices of
$\Gamma _1$
and
$\Gamma _2$
are relatively isomorphic to either
$\Gamma (\kappa ,1)$
or
$\Gamma _{\textsf{top}}$
which are symmetric. Therefore,
$\Gamma _1$
and
$\Gamma _2$
are symmetric.
When
$(p\,\textsf{mod}\, q)=1$
, the minimum grading of a vertex in
$\Gamma (p,q)$
is 0. The minimum grading for a vertex in
$\Gamma _1$
is 1. The minimum grading for a vertex in
$\Gamma _2$
is
$\kappa $
. Therefore, no bottoms of
$\Gamma (p,q)$
are contained in
$\Gamma _1$
or
$\Gamma _2$
. Thus, (R5) is satisfied.
In conclusion,
$\Gamma (p,q)$
is a pre-RTFN pair when
$q=1$
or
$(p\,\textsf{mod}\, q)=1$
.
Let
$(p,q)$
be a relevant co-prime pair with
$q>1$
and
$(p\,\textsf{mod}\, q)>1$
, and let
$(p^*,q^*)$
be the co-prime pair defined by Lemma 4.5. Suppose
$(p^*,q^*)$
is a pre-RTFN pair, so there are a positive integer
$N^*$
and subgraphs
$$\begin{align*}\Gamma^*_0,\ldots,\Gamma^*_{N^*}, \end{align*}$$
$$\begin{align*}\Upsilon^*_1,\ldots,\Upsilon^*_{N^*}, \end{align*}$$
and
$$\begin{align*}\Omega^*_1,\ldots,\Omega^*_{N^*}, \end{align*}$$
and integers
$$\begin{align*}n^*_1,\ldots,n^*_{N^*}, \end{align*}$$
To show that
$(p,q)$
is a pre-RTFN pair, we need to define N, the subgraphs
$\{\Gamma _i\}^N_{i=0}$
,
$\{\Upsilon _i\}^N_{i=1}$
, and
$\{\Omega _i\}^N_{i=1}$
, and the integers
$\{n_i\}^N_1$
for
$(p,q)$
. This choice depends on how expansion affects the nested repeating pattern of summits in
$\overline {\Gamma }(p^*,q^*)$
.
Define
$\kappa $
and
$\kappa '$
as in (4.2) and (4.3), so
$\overline {\Gamma }(p,q)\cong E(\overline {\Gamma }(p^*,q^*),\kappa ,\kappa ')$
by Proposition 4.9. Suppose
$\Gamma ^*$
is a proper subgraph of
$\Gamma (p^*,q^*)$
, so
$\Gamma ^*$
naturally embeds into
$\overline {\Gamma }(p^*,q^*)$
. Let
$e^*$
be the sign of the edge immediately preceding
$\Gamma ^*$
in
$\overline {\Gamma }(p^*,q^*)$
. For simplicity of notation, we define
$$\begin{align*}\tilde{E}(\Gamma^*):=\tilde{E}(\Gamma^*,\kappa,\kappa',e^*), \end{align*}$$
and when
$\Gamma ^*$
is closable, define
$$\begin{align*}E(\Gamma^*):=E(\Gamma^*,\kappa,\kappa'). \end{align*}$$
Notice that
$E(\Gamma ^*)$
and
$\tilde {E}(\Gamma ^*)$
are not always the same.
Ideally, when
$i=0,\ldots , N^*$
, we want to define
$\Gamma _i$
to be
$E(\Gamma ^*_i)$
and set
$n_i$
equal to
$n_i^*$
. Then, we examine the structure of
$E(\Gamma ^*_{N^*})$
. The hope is that since the expansion operation is compatible with concatenation (see Lemma 4.8), we can leverage the pre-RTFN pair properties of the
$\Gamma ^*_i$
,
$\Upsilon ^*_i$
, and
$\Omega ^*_i$
sequences to prove that
$\Gamma _i$
,
$\Upsilon _i$
, and
$\Omega _i$
also satisfy the pre-RTFN properties. This turns out to be more subtle than one might first expect.
For all
$i=1,\ldots ,N^*$
,
$$\begin{align*}\Gamma^*_{i-1}\cong\Upsilon^*_i*(\Gamma^*_i)^{n^*_i}*\Omega^*_i \end{align*}$$
by (R3) for
$(p^*,q^*)$
. By Lemma 4.8,
$$ \begin{align} \tilde{E}(\Gamma^*_{i-1})\cong \tilde{E}(\Upsilon^*_i)*\tilde{E}((\Gamma^*_i)^{n^*_i})*\tilde{E}(\Omega^*_i). \end{align} $$
However, if
$\Gamma _i$
is
$E(\Gamma ^*_i)$
, then
$\Gamma _i^{n_i}$
is
$E(\Gamma ^*_i)^{n^*_i}$
, and
$E(\Gamma ^*_i)^{n^*_i}$
may not be equal to
$\tilde {E}((\Gamma ^*_i)^{n^*_i})$
. We show that they can be made equal by adding or removing
$\kappa $
edges. See Figure 20.
Figure 20: Expanding
$\Gamma (4,3)$
to
$\Gamma (26,11)$
.
Consider
$i\in \{1,\ldots ,N^*\}$
. Define
$\tilde {\Gamma }_i:=\tilde {E}((\Gamma ^*_i)^{n^*_i})$
. Let
$\tilde {\Gamma }^+_i$
be
$\tilde {\Gamma }_i$
with the
$\kappa $
edges in
$\Gamma (p,q)$
preceding the first vertex of
$\tilde {E}((\Gamma ^*_i)^{n^*_i})$
added. Let
$\tilde {\Gamma }^-_i$
be
$\tilde {\Gamma }_i$
with the first
$\kappa $
vertices with their incident edges removed.
Lemma 5.9 One of
$\tilde {\Gamma }_i$
,
$\tilde {\Gamma }^+_i$
, or
$\tilde {\Gamma }^-_i$
is isomorphic to
$E(\Gamma ^*_i)^{n^*_i}$
.
Proof Consider
$(\Gamma ^*_i)^{n_i}$
as a subgraph of
$\overline {\Gamma }(p^*,q^*)$
. For all but the first
$\Gamma ^*_i$
in
$(\Gamma ^*_i)^{n_i}$
,
$\tilde {E}(\Gamma ^*_i)\cong E(\Gamma ^*_i)$
, so
$$\begin{align*}\tilde{\Gamma}_i\cong\tilde{E}(\Gamma^*_i)*(E(\Gamma^*_i))^{n^*_i-1}. \end{align*}$$
Let
$e_0$
be the sign of the first edge in
$\Gamma ^*_i$
, and define
$$\begin{align*}\Gamma_{\textrm{short}}:= \begin{cases} \tilde{E}(\Gamma^*_i,\kappa,\kappa',+1), & (e_0\text{ is 1 and } \kappa'\text{ is even) or }(e_0\text{ is -1 and } \kappa'\text{ is odd})\\ \tilde{E}(\Gamma^*_i,\kappa,\kappa',-1), & (e_0\text{ is 1 and } \kappa'\text{ is odd) or }(e_0\text{ is -1 and } \kappa'\text{ is even}) \end{cases} \end{align*}$$
and
$$\begin{align*}\Gamma_{\textrm{long}}:= \begin{cases} \tilde{E}(\Gamma^*_i,\kappa,\kappa',-1), & (e_0\text{ is 1 and } \kappa'\text{ is even) or }(e_0\text{ is -1 and } \kappa'\text{ is odd}),\\ \tilde{E}(\Gamma^*_i,\kappa,\kappa',+1), & (e_0\text{ is 1 and } \kappa'\text{ is odd) or }(e_0\text{ is -1 and } \kappa'\text{ is even}). \end{cases} \end{align*}$$
Notice that
$\Gamma _{\textrm{long}}$
is a
$\kappa $
-segment concatenated with
$\Gamma _{\textrm{short}}$
. Each of
$\tilde {E}(\Gamma ^*_i)$
and
$E(\Gamma ^*_i)$
is isomorphic to
$\Gamma _{\textrm{long}}$
or
$\Gamma _{\textrm{short}}$
.
When
$\tilde {E}(\Gamma ^*_i)$
is isomorphic to
$E(\Gamma ^*_i)$
,
$\tilde {\Gamma }_i$
is isomorphic to
$E(\Gamma ^*_i)^{n^*_i}$
.
When
$\tilde {E}(\Gamma ^*_i)$
is isomorphic to
$\Gamma _{\textrm{short}}$
and
$E(\Gamma ^*_i)$
is isomorphic to
$\Gamma _{\textrm{long}}$
,
$\tilde {\Gamma }^-_i$
is isomorphic to
$E(\Gamma ^*_i)^{n^*_i}$
.
When
$\tilde {E}(\Gamma ^*_i)$
is isomorphic to
$\Gamma _{\textrm{long}}$
and
$E(\Gamma ^*_i)$
is isomorphic to
$\Gamma _{\textrm{short}}$
,
$\tilde {\Gamma }^+_i$
is isomorphic to
$E(\Gamma ^*_i)^{n^*_i}$
.
Now, we analyze the structure of
$E(\Gamma ^*_{N^*})$
. In particular, we want to know where the summits
$\overline {\Gamma }(p,q)$
are located. By Corollary 5.7, the leading summits of
$\overline {\Gamma }(p,q)$
correspond to the summits of
$\overline {\Gamma }(p^*,q^*)$
. Now, we consider the nonleading summits in
$\overline {\Gamma }(p,q)$
. Let d be
$\kappa '$
or
$\kappa '-1$
whichever is even.
Let
$\Gamma _{\textsf{top}}$
and
$\Gamma _{\textsf{top}}^*$
be defined for
$(p,q)$
and
$(p^*,q^*)$
, respectively, as shown in Figure 13. By (R2),
$\Gamma ^*_{N^*}$
is isomorphic to
$\Gamma _{\textsf{top}}^*$
. By definition,
$E(\Gamma _{\textsf{top}}^*)$
is the concatenation of a
$\kappa $
-block of even length, a positive
$(\kappa +1)$
-segment, another
$\kappa $
-block of even length, and a negative
$(\kappa +1)$
-segment. It follows that every summit in
$\overline {\Gamma }(p^*,q^*)$
corresponds to
$d/2+1$
summits in
$\Gamma (p,q)$
.
We are ready to define N,
$\{\Gamma _i\}^N_0$
,
$\{\Upsilon _i\}^N_0$
,
$\{\Omega _i\}^N_0$
and
$\{n_i\}^N_1$
. Let
$\Gamma $
be an incremental path with vertex set
$\{V_0,\ldots ,V_n\}$
, and let
$\Upsilon $
be a connected subgraph of
$\Gamma $
with vertices
$V_i,\ldots ,V_{i+k}$
. Define
$\textrm{Left}(\Gamma ,\Upsilon )$
to be
$\omega (\Gamma ,V_0, V_i)$
, and define
$\textrm{Right}(\Gamma ,\Upsilon )$
to be
$\omega (\Gamma ,V_{i+k}, V_n)$
.
For each
$i=1,\ldots ,N^*$
, exactly one of the subgraphs
$\tilde {\Gamma }_i$
,
$\tilde {\Gamma }^+_i$
, or
$\tilde {\Gamma }^-_i$
is isomorphic to
$E(\Gamma ^*_i)^{n^*_i}$
by Lemma 5.9. Call this subgraph
$\Gamma ^{\prime }_i$
. For each
$i=0,\ldots ,N^*$
, we make the following choices.
-
• Let
$\Gamma _i=E(\Gamma ^*_i)$
. -
• Let
$n_i=n^*_i$
. -
• Let
$\Upsilon _i=\textrm{Left}(\Gamma _{i-1},\Gamma ^{\prime }_i)$
. -
• Let
$\Omega _i=\textrm{Right}(\Gamma _{i-1},\Gamma ^{\prime }_i)$
.
Note that since
$\Gamma _{i-1}$
is
$E(\Gamma ^*_{i-1})$
,
$\Gamma ^{\prime }_i$
is a subgraph of
$\Gamma _{i-1}$
by (5.9).
Let
$\{Q_0,\ldots ,Q_n\}$
be the vertex set of
$\Gamma _{N^*}$
. Since
$\Gamma _{N^*}=E(\Gamma ^*_{N^*})$
,
$$\begin{align*}n=2(\kappa+d\kappa+1). \end{align*}$$
Suppose
$\kappa '=1$
, so
$n=2(\kappa +1)$
.
-
• Let
$N=N^*+1$
. -
• Let
$\Gamma _{N}=\Gamma _{\textsf{top}}$
. -
• Let
$n_{N}=d/2+1$
. -
• Let
$\Upsilon _N=\omega (\Gamma _{N^*-1},Q_0,Q_{\kappa })$
. -
• Let
$\Omega _N=\omega (\Gamma _{N^*-1},Q_{\kappa +2},Q_{n})$
.
Suppose
$\kappa =1$
.
-
• Let
$N=N^*+1$
. -
• Let
$\Gamma _{N}=\Gamma _{\textsf{top}}$
. -
• Let
$n_{N}=d/2+1$
. -
• Let
$\Upsilon _N=\omega (\Gamma _{N^*-1},Q_{d},Q_{d+1})$
. -
• Let
$\Omega _N=\omega (\Gamma _{N^*-1},Q_{n-1},Q_n)$
.
Suppose
$\kappa '>1$
and
$\kappa>1$
.
-
• Let
$N=N^*+2$
. -
• Let
$\Gamma _{N-1}$
be a positive
$\kappa $
-segment followed by a negative
$\kappa $
-segment. -
• Let
$\Gamma _{N}=\Gamma _{\textsf{top}}$
. -
• Let
$n_{N-1}=d/2+1$
. -
• Let
$n_{N}=1$
. -
• Let
$\Upsilon _{N-1}=\omega (\Gamma _{N^*-1},Q_{d\kappa },Q_{d\kappa +1})$
. -
• Let
$\Omega _{N-1}=\omega (\Gamma _{N^*-1},Q_{2d\kappa +3},Q_n)$
. -
• Let
$\Upsilon _N=\omega (\Gamma _{N^*-1},Q_{d\kappa +1},Q_{d\kappa +\kappa })$
. -
• Let
$\Omega _N=\omega (\Gamma _{N^*-1},Q_{d\kappa +\kappa +2},Q_{d\kappa +2\kappa +1})$
.
Lemma 5.10 The integers
$\{n_i\}^N_{i=1}$
and the subgraphs
$\{\Gamma _i\}^N_{i=0}$
,
$\{\Upsilon _i\}^N_{i=1}$
, and
$\{\Omega _i\}^N_{i=1}$
satisfy (R1)–(R4).
Proof Since
$\Gamma ^*_0\cong \Gamma (p^*,q^*)$
,
$$\begin{align*}\Gamma_0\cong E(\Gamma(p^*,q^*))\cong\Gamma(p,q), \end{align*}$$
so (R1) is satisfied.
By definition,
$\Gamma _N\cong \Gamma _{\textsf{top}}$
, so (R2) is satisfied.
When
$N^*<i\leq N$
, (R3) and (R4) are satisfied by proofs similar to those in Lemma 5.8.
Suppose
$i\in \{1,\ldots ,N^*\}$
:
$$ \begin{align*} \Gamma_{i-1}&=\textrm{Left}(\Gamma_{i-1},\Gamma^{\prime}_i)*\Gamma^{\prime}_i*\textrm{Right}(\Gamma_{i-1},\Gamma^{\prime}_i)\\ &\cong\Upsilon_i*E(\Gamma^*_{i})^{n^*_i}*\Omega_i\\ &=\Upsilon_i*\Gamma_{i}^{n_i}*\Omega_i. \end{align*} $$
Therefore, (R3) is satisfied.
$\tilde {E}((\Gamma ^*_i)^{n^*_i})$
is
$\Gamma ^{\prime }_i$
possibly with
$\kappa $
edges added to or removed from the beginning. Also,
$$\begin{align*}\Upsilon_i*\Gamma^{\prime}_{i}*\Omega_i\cong\Gamma_{i-1}\cong\tilde{E}(\Gamma^*_{i-1}) \cong\tilde{E}(\Upsilon^*_i)*\tilde{E}((\Gamma^*_{i})^{n^*_i})*\tilde{E}(\Omega^*_i). \end{align*}$$
It follows that
$\Omega _i$
is
$\tilde {E}(\Omega ^*_i)$
and
$\Upsilon _i$
is
$\tilde {E}(\Upsilon ^*_i)$
with possibly
$\kappa $
edges added to or removed from the end (see Figure 20).
Since no summits of
$\Gamma (p^*,q^*)$
are in
$\Upsilon ^*_i$
, there are no summits of
$\Gamma (p,q)$
in
$\tilde {E}(\Upsilon ^*_i)$
. It follows that if
$\Upsilon _i$
is equal to
$\tilde {E}(\Upsilon ^*_i)$
or is
$\tilde {E}(\Upsilon ^*_i)$
with edges removed, then
$\Upsilon _i$
contains no summits of
$\Gamma (p,q)$
.
Consider the case when
$\Upsilon _i$
is
$\tilde {E}(\Upsilon ^*_i)$
with a
$\kappa $
-segment added. Let P be the vertex at the end of
$\tilde {E}(\Upsilon ^*_i)$
. If the segment added is negative, then the gradings of the vertices added to
$\tilde {E}(\Upsilon ^*_i)$
are less than
$\textsf{gr}(P)$
, so they cannot be summits.
If the segment added is positive, then P is at the end of either a
$\kappa $
-segment or a
$(\kappa +1)$
-segment. In either case, the maximum grading of a vertex in
$\tilde {E}(\Upsilon ^*_i)$
is at least
$\textsf{gr}(P)+\kappa $
. Since none of the vertices of
$\tilde {E}(\Upsilon ^*_i)$
are summits of
$\Gamma (p,q)$
, the grading of a summit of
$\Gamma (p,q)$
must be bigger than
$\textsf{gr}(P)+\kappa $
. Since only
$\kappa $
edges are being added, the gradings of the vertices added to
$\tilde {E}(\Upsilon ^*_i)$
are no bigger than
$\textsf{gr}(P)+\kappa $
, so they cannot be summits of
$\Gamma (p,q)$
. Thus, there are no summits in
$\Upsilon _i$
.
Since no summits are in
$\Omega ^*_i$
, there are no summits
$\tilde {E}(\Omega ^*_i)\cong \Omega _i$
. Therefore, (R4) is satisfied.
Lemma 5.11 The subgraphs
$\{\Gamma _i\}^N_0$
satisfy (R5).
Proof First, we show that
$\Gamma _i$
has no bottoms for each
$i=1,\ldots , N$
. Since
$N^*\geq 1$
,
$\Gamma _1=E(\Gamma ^*_1)$
. Since
$\Gamma ^*_1$
has no bottoms,
$\Gamma _1$
does not have bottoms. When
$1\leq i\leq N$
,
$$\begin{align*}\Gamma_{i-1}\cong\Upsilon_i\Gamma_i^{n_i}*\Omega_i, \end{align*}$$
so
$\Gamma _i$
is a subgraph of
$\Gamma _1$
. Therefore,
$\Gamma _i$
has no bottoms.
Suppose
$0 \leq i \leq N$
. Here, we show that
$\Gamma _i$
is symmetric. When
$i>N^*$
,
$\Gamma _i$
is either the concatenation of a positive
$\kappa $
-segment and a negative
$\kappa $
-segment or
$\Gamma _{\textsf{top}}$
. In both cases,
$\Gamma _i$
can be shown to be symmetric by an argument similar to those used in the proof of Lemma 5.8.
Suppose
$0\leq i\leq N^*$
. In this case,
$\Gamma _i=E(\Gamma ^*_i)$
. Our goal is to show that since
$\Gamma ^*_i$
is symmetric,
$\Gamma _i$
is also symmetric.
Since
$\Gamma ^*_i$
is symmetric, there are an order-reversing bijection
$\phi ^*$
on the set of vertices of
$\textsf{cl}(\Gamma ^*_i)$
and an integer
$k^*$
such that for each
$P^*$
in
$\textsf{cl}(\Gamma ^*_i)$
,
$$ \begin{align} \textsf{gr}(P^*)+\textsf{gr}(\phi^*(P^*))=k^*. \end{align} $$
Let
$V_L$
and
$V_T$
be the sets of leading and trailing vertices of
$\textsf{cl}(\Gamma _i)$
, respectively, and let
$V^*$
be the vertex set of
$\textsf{cl}(\Gamma ^*_i)$
. Define
$\phi $
to be the unique order-reversing bijection on the vertices of
$\textsf{cl}(\Gamma _i)$
such that the following diagram commutes:
In particular,
$\phi $
maps leading vertices bijectively to trailing vertices (see Figure 21). Let
$P_S$
be a leading summit of
$\Gamma _i$
, and let
$P^*_S=f_L(P_S)$
in
$\Gamma ^*_i$
.
Figure 21: The incremental cycles
$\textsf{cl}(\Gamma _i)$
(top) and
$\textsf{cl}(\Gamma ^*_i)$
(bottom) are shown. P is a leading vertex, and
$f_L(P)$
is denoted
$P^*$
.
$\phi (P)$
is a trailing vertex, and
$\phi ^*(P^*)=f_T(\phi (P))$
.
Let
$k=\textsf{gr}(P_S)+\textsf{gr}(\phi (P_S))$
, and let P be an arbitrary vertex in
$\Gamma _i$
. The goal is to show that
$\textsf{gr}(P)+\textsf{gr}(\phi (P))=k$
, which is done in four cases.
Case 1. Suppose P is a leading vertex and
$P^*:=f_L(P)$
has the same vertex type as P, either a peak (type
$(-+)$
) or valley (type
$(+-)$
). Recall from Figure 16 how the automorphism
$\phi ^*$
affects vertex type. If
$P^*$
is of type
$(-+)$
, then
$\phi ^*(P^*)$
is of type
$(+-)$
, and if
$P^*$
is of type
$(+-)$
, then
$\phi ^*(P^*)$
is of type
$(-+)$
. Therefore, either
$f_L^{-1}(P^*)$
and
$f_T^{-1}(P^*)$
are both peaks and
$f_L^{-1}(\phi ^*(P^*))$
and
$f_T^{-1}(\phi ^*(P^*))$
are both valleys or
$f_L^{-1}(P^*)$
and
$f_T^{-1}(P^*)$
are both valleys and
$f_L^{-1}(\phi ^*(P^*))$
and
$f_T^{-1}(\phi ^*(P^*))$
are both peaks. In either case,
$$ \begin{align} \textsf{gr}(f_L^{-1}(\phi^*(P^*)))=\textsf{gr}(f_T^{-1}(\phi^*(P^*))). \end{align} $$
Thus,
$$ \begin{align*} \textsf{gr}(P)+\textsf{gr}(\phi(P))-k&=\textsf{gr}(P)-\textsf{gr}(P_S)+\textsf{gr}(\phi(P))-\textsf{gr}(\phi(P_S))\\ &=\textsf{gr}(f_L^{-1}(P^*))-\textsf{gr}(f_L^{-1}(P^*_S))\\ &\quad +\textsf{gr}(\phi(f_L^{-1}(P^*)))-\textsf{gr}(\phi(f_L^{-1}(P^*_S)))\\ &=\textsf{gr}(f_L^{-1}(P^*))-\textsf{gr}(f_L^{-1}(P^*_S))\\ &\quad +\textsf{gr}(f_T^{-1}(\phi^*(P^*)))-\textsf{gr}(f_T^{-1}(\phi^*(P^*_S))). \end{align*} $$
Summits are of type
$(-+)$
, so by (5.11),
$$\begin{align*}\textsf{gr}(f_T^{-1}(\phi^*(P^*)))-\textsf{gr}(f_T^{-1}(\phi^*(P^*_S)))=\textsf{gr}(f_L^{-1}(\phi^*(P^*)))-\textsf{gr}(f_L^{-1}(\phi^*(P^*_S))). \end{align*}$$
By Proposition 5.6 and (5.10),
$$ \begin{align*} \textsf{gr}(P)+\textsf{gr}(\phi(P))-k&=\textsf{gr}(f_L^{-1}(P^*))-\textsf{gr}(f_L^{-1}(P^*_S))\\ &\quad +\textsf{gr}(f_L^{-1}(\phi^*(P^*)))-\textsf{gr}(f_L^{-1}(\phi^*(P^*_S)))\\ &=\textsf{gr}(P^*)-\textsf{gr}(P^*_S)+\textsf{gr}(\phi^*(P^*))-\textsf{gr}(\phi^*(P^*_S))\\ &=\textsf{gr}(P^*)+\textsf{gr}(\phi^*(P^*))-(\textsf{gr}(P^*_S)+\textsf{gr}(\phi^*(P^*_S)))\\ &=k^*-k^*=0. \end{align*} $$
Therefore,
$$\begin{align*}\textsf{gr}(P)+\textsf{gr}(\phi(P))=k. \end{align*}$$
Case 2. Suppose P is a leading peak and
$P^*:=f_L(P)$
has type
$(++)$
. In this case,
$f_L^{-1}(P^*)$
and
$f_L^{-1}(\phi ^*(P^*))$
are both peaks and
$f_T^{-1}(P^*)$
and
$f_T^{-1}(\phi ^*(P^*))$
are both valleys. Thus,
$$\begin{align*}\textsf{gr}(f_L^{-1}(\phi^*(P^*)))=\textsf{gr}(f_T^{-1}(\phi^*(P^*)))+\kappa, \end{align*}$$
and
$$ \begin{align*} \textsf{gr}(P)+\textsf{gr}(\phi(P))-k&=\textsf{gr}(P)-\textsf{gr}(P_S)+\textsf{gr}(\phi(P))-\textsf{gr}(\phi(P_S))\\ &=\textsf{gr}(f_L^{-1}(P^*))-\textsf{gr}(f_L^{-1}(P^*_S))\\ &\quad +\textsf{gr}(\phi(f_L^{-1}(P^*)))-\textsf{gr}(\phi(f_L^{-1}(P^*_S)))\\ &=\textsf{gr}(f_L^{-1}(P^*))-\textsf{gr}(f_L^{-1}(P^*_S))\\ &\quad +\textsf{gr}(f_T^{-1}(\phi^*(P^*)))-\textsf{gr}(f_T^{-1}(\phi^*(P^*_S)))\\ &=\textsf{gr}(f_L^{-1}(P^*))-\textsf{gr}(f_L^{-1}(P^*_S))\\ &\quad +\textsf{gr}(f_L^{-1}(\phi^*(P^*)))-\textsf{gr}(f_L^{-1}(\phi^*(P^*_S)))\\ &=\textsf{gr}(P^*)-\textsf{gr}(P^*_S)+\textsf{gr}(\phi^*(P^*))-\textsf{gr}(\phi^*(P^*_S))\\ &=0. \end{align*} $$
Case 3. Suppose P is a leading valley and
$P^*:=f_L(P)$
has type
$(--)$
. In this case,
$f_T^{-1}(P^*)$
and
$f_T^{-1}(\phi ^*(P^*))$
are both peaks and
$f_L^{-1}(P^*)$
and
$f_L^{-1}(\phi ^*(P^*))$
are both valleys. Thus,
$$\begin{align*}\textsf{gr}(f_L^{-1}(\phi^*(P^*)))=\textsf{gr}(f_T^{-1}(\phi^*(P^*)))-\kappa, \end{align*}$$
and
$$ \begin{align*} \textsf{gr}(P)+\textsf{gr}(\phi(P))-k&=\textsf{gr}(P)-\textsf{gr}(P_S)+\textsf{gr}(\phi(P))-\textsf{gr}(\phi(P_S))\\ &=\textsf{gr}(f_L^{-1}(P^*))-\textsf{gr}(f_L^{-1}(P^*_S))\\ &\quad +\textsf{gr}(\phi(f_L^{-1}(P^*)))-\textsf{gr}(\phi(f_L^{-1}(P^*_S)))\\ &=\textsf{gr}(f_L^{-1}(P^*))-\textsf{gr}(f_L^{-1}(P^*_S))\\ &\quad +\textsf{gr}(f_T^{-1}(\phi^*(P^*)))-\textsf{gr}(f_T^{-1}(\phi^*(P^*_S)))\\ &=\textsf{gr}(f_L^{-1}(P^*))-\textsf{gr}(f_L^{-1}(P^*_S))\\ &\quad +\textsf{gr}(f_L^{-1}(\phi^*(P^*)))-\textsf{gr}(f_L^{-1}(\phi^*(P^*_S)))\\ &=\textsf{gr}(P^*)-\textsf{gr}(P^*_S)+\textsf{gr}(\phi^*(P^*))-\textsf{gr}(\phi^*(P^*_S))\\ &=0. \end{align*} $$
Case 4. Suppose P is not a leading vertex. Let
$P'$
be the leading vertex in
$\textsf{cl}(\Gamma _i)$
such that the length of the path
$\omega (\textsf{cl}(\Gamma _i),P',P)$
is minimal. It follows that
$\omega (\textsf{cl}(\Gamma _i),P',P)$
is isomorphic to a subgraph of a
$\kappa $
-block as in Figure 22. In particular, there are no leading vertices between
$P'$
and P in
$\textsf{cl}(\Gamma _i)$
; therefore, there are no trailing vertices between
$\phi (P)$
and
$\phi (P')$
in
$\textsf{cl}(\Gamma _i)$
, so
$\omega (\textsf{cl}(\Gamma _i),\phi (P),\phi (P'))$
is also isomorphic to a subgraph of a
$\kappa $
-block.
Figure 22: In solid black, the subgraphs
$\omega (\textsf{cl}(\Gamma _i),P',P)$
(left) and
$\omega (\textsf{cl}(\Gamma _i),\phi (P),\phi (P'))$
(right) are shown. The dashed gray arrows are other edges in
$\textsf{cl}(\Gamma _i)$
. The case shown is when
$P'$
is a peak.
Let Q be the closest vertex (in the forward direction) to P with grading
$\textsf{gr}(Q)=\textsf{gr}(P')$
. When
$P'$
is a peak, Q is a peak. Likewise, when
$P'$
is a valley, Q is a valley. Define d be the distance (going forward) from
$P'$
to Q. Since P is in a
$\kappa $
-block which starts at
$P'$
, Q and P lie on the same segment, so
$$\begin{align*}\textsf{gr}(Q)-\textsf{gr}(P)=\left\{ \begin{array}{ll} d,&\text{when }Q\text{ is a peak,}\\ -d,&\text{when }Q\text{ is a valley;} \end{array} \right. \end{align*}$$
also,
$\phi (Q)$
and
$\phi (P)$
lie on the same segment, so
$$\begin{align*}\textsf{gr}(\phi(Q))-\textsf{gr}(\phi(P))=\left\{ \begin{array}{ll} -d,&\text{when }Q\text{ is a peak,}\\ d,&\text{when }Q\text{ is a valley.} \end{array} \right. \end{align*}$$
If
$P'$
and Q are peaks, then
$$\begin{align*}\textsf{gr}(P)=\textsf{gr}(Q)-d=\textsf{gr}(P')-d \end{align*}$$
and
$$\begin{align*}\textsf{gr}(\phi(P))=\textsf{gr}(\phi(Q))+d=\textsf{gr}(\phi(P'))+d. \end{align*}$$
If
$P'$
and Q are valleys, then
$$\begin{align*}\textsf{gr}(P)=\textsf{gr}(Q)+d=\textsf{gr}(P')+d \end{align*}$$
and
$$\begin{align*}\textsf{gr}(\phi(P))=\textsf{gr}(\phi(Q))-d=\textsf{gr}(\phi(P'))-d. \end{align*}$$
In both cases,
$$\begin{align*}\textsf{gr}(P)+\textsf{gr}(\phi(P))=\textsf{gr}(P')+\textsf{gr}(\phi(P'))=k. \end{align*}$$
Therefore, for every vertex P in
$\textsf{cl}(\Gamma _i)$
,
$\textsf{gr}(P)+\textsf{gr}(\phi (P))=k$
, so
$\Gamma _i$
is symmetric.
Proof of Lemma 3.5
By Lemma 5.4, it is sufficient to show that every relevant co-prime pair is a pre-RTFN pair.
Let
$(p,q)$
be a relevant co-prime pair. If
$q=1$
or
$(p\,\textsf{mod}\, q)=1$
with q positive, then
$(p,q)$
is a pre-RTFN pair by Lemma 5.8. If
$q=-1$
, then
$(p,q)$
is a pre-RTFN pair by Lemma 5.3.
Suppose
$|q|\neq 1$
and
$(p\,\textsf{mod}\, q)>1$
, and assume every relevant co-prime pair
$(p',q')$
with
$|q'|<|q|$
is a pre-RTFN pair. When q is positive, define the relevant co-prime pair
$(p^*,q^*)$
as in Lemma 4.5. Since
$|q^*|<|q|$
,
$(p^*,q^*)$
is a pre-RTFN pair. By Lemmas 5.10 and 5.11,
$(p,q)$
is also pre-RTFN pair. When q is negative, the pair
$(p,-q)$
is a pre-RTFN pair by the above argument. Thus,
$(p,q)$
is a pre-RTFN pair by Lemma 5.3.
By strong induction, every relevant co-prime pair
$(p,q)$
with p positive and q odd is a pre-RTFN pair.
A Background on presentation matrices
Let R be a PID. Suppose X is an R-module with presentation
$$\begin{align*}\langle x_1,\ldots,x_n | s_1,\ldots,s_m\rangle. \end{align*}$$
For each i,
$$\begin{align*}s_i=\sum_{j=1}^n r_{i,j}x_j, \end{align*}$$
where each
$r_{i,j}$
is in R. The matrix of
$r_{i,j}$
coefficients
$$\begin{align*}\left( \begin{array}{ccc} r_{1,1} & \cdots & r_{1,n} \\ \vdots & & \vdots \\ r_{m,1} & \cdots & r_{m,n} \end{array} \right) \end{align*}$$
is called a presentation matrix of X. Suppose A is a presentation matrix of X. Performing row and column operations on A will always produce another presentation matrix of X.
Using row and column operations, any matrix over a PID can be put in the form
where each
$d_i$
is nonzero and
$d_i$
divides
$d_{i+1}$
for each
$i=1,\ldots ,k-1$
. This is called the Smith normal form of a matrix.
When A is the presentation matrix of X and
$d_1,\ldots ,d_k$
are the diagonal entries of the Smith normal form of A,
$$ \begin{align} X\cong R^{n-k}\oplus \frac{R}{d_1R}\oplus\cdots\oplus\frac{R}{d_kR}. \end{align} $$
The
$d_i$
which are not units are the invariant factors of X.
The following lemma plays a key role in showing that elements in a para-free group are homologically primitive.
Lemma A.1 Suppose X is an R-module with an
$m\times n$
presentation matrix A of full rank. If the greatest common divisor of every
$m\times m$
minor of A is a unit, then X is a free R-module. Otherwise, the greatest common divisor of every
$m\times m$
minor of A is equal to the product of the invariant factors of X up to multiplication by a unit.
Proof Let B be the Smith normal form of A. Since A has full row rank, B has no extra rows of zeros, so B has the following form:
$$\begin{align*}B=\left( \begin{array}{ccc|c} d_1 & & & \\ & \ddots & & {\huge{\text 0}}\\ & & d_m& \end{array} \right). \end{align*}$$
For any
$m\times n$
matrix with entries in R, the greatest common divisor of its
$m\times m$
minors is invariant under row and column operations up to multiplication by a unit. Therefore, up to a unit, the greatest common divisor of the
$m\times m$
minors of A is
$\prod _{i=1}^m d_i$
. When
$\prod _{i=1}^m d_i$
is a unit, each
$d_i$
is a unit, so by (A.1), X is a free R-module. If
$\prod _{i=1}^m d_i$
is not a unit, it is the product of the invariant factors of X up to multiplication by a unit.
Acknowledgment
The author would like to thank Cameron Gordon for his guidance and encouragement throughout this project. The author would also like to thank Ahmad Issa for providing the example of the knot with all real positive roots. The author would also like to thank Hannah Turner for many helpful writing suggestions and support. The author would also like to thank the Canadian Journal of Mathematics referee for noticing a key oversight in the statement of Lemma 3.5 and for the many other excellent editorial suggestions made in their very thorough review. The author would also like to thank Jae Choon Cha, Charles Livingston, and Allison Moore for creating and maintaining KnotInfo [Reference Livingston and Moore14] and LinkInfo [Reference Livingston and Moore15], which were invaluable to this project.
