Generalized classes of suborbital graphs for the congruence subgroups of the modular group
Let Г be the modular group. We extend a nontrivial Г-invariant equivalence relation on Q to a general relation by replacing the group Г₀(n) by Гк(n), and determine the suborbital graph Fᴷu,n, an extended concept of the graph Fu,n. We investigate several properties of the graph, such as, connectivity...
Збережено в:
| Опубліковано в: : | Algebra and Discrete Mathematics |
|---|---|
| Дата: | 2019 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2019
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/188419 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Generalized classes of suborbital graphs for the congruence subgroups of the modular group / P. Jaipong, W. Tapanyo // Algebra and Discrete Mathematics. — 2019. — Vol. 27, № 1. — С. 20–36. — Бібліогр.: 14 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-188419 |
|---|---|
| record_format |
dspace |
| spelling |
Jaipong, P. Tapanyo, W. 2023-02-28T18:45:07Z 2023-02-28T18:45:07Z 2019 Generalized classes of suborbital graphs for the congruence subgroups of the modular group / P. Jaipong, W. Tapanyo // Algebra and Discrete Mathematics. — 2019. — Vol. 27, № 1. — С. 20–36. — Бібліогр.: 14 назв. — англ. 1726-3255 2010 MSC: Primary 05C20, 05C40, 05C63; Secondary 05C05, 05C60, 20H05. https://nasplib.isofts.kiev.ua/handle/123456789/188419 Let Г be the modular group. We extend a nontrivial Г-invariant equivalence relation on Q to a general relation by replacing the group Г₀(n) by Гк(n), and determine the suborbital graph Fᴷu,n, an extended concept of the graph Fu,n. We investigate several properties of the graph, such as, connectivity, forest conditions, and the relation between circuits of the graph and elliptic elements of the group Гк(n). We also provide the discussion on suborbital graphs for conjugate subgroups of Г. This research was supported by Chiang Mai University. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics Generalized classes of suborbital graphs for the congruence subgroups of the modular group Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Generalized classes of suborbital graphs for the congruence subgroups of the modular group |
| spellingShingle |
Generalized classes of suborbital graphs for the congruence subgroups of the modular group Jaipong, P. Tapanyo, W. |
| title_short |
Generalized classes of suborbital graphs for the congruence subgroups of the modular group |
| title_full |
Generalized classes of suborbital graphs for the congruence subgroups of the modular group |
| title_fullStr |
Generalized classes of suborbital graphs for the congruence subgroups of the modular group |
| title_full_unstemmed |
Generalized classes of suborbital graphs for the congruence subgroups of the modular group |
| title_sort |
generalized classes of suborbital graphs for the congruence subgroups of the modular group |
| author |
Jaipong, P. Tapanyo, W. |
| author_facet |
Jaipong, P. Tapanyo, W. |
| publishDate |
2019 |
| language |
English |
| container_title |
Algebra and Discrete Mathematics |
| publisher |
Інститут прикладної математики і механіки НАН України |
| format |
Article |
| description |
Let Г be the modular group. We extend a nontrivial Г-invariant equivalence relation on Q to a general relation by replacing the group Г₀(n) by Гк(n), and determine the suborbital graph Fᴷu,n, an extended concept of the graph Fu,n. We investigate several properties of the graph, such as, connectivity, forest conditions, and the relation between circuits of the graph and elliptic elements of the group Гк(n). We also provide the discussion on suborbital graphs for conjugate subgroups of Г.
|
| issn |
1726-3255 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/188419 |
| citation_txt |
Generalized classes of suborbital graphs for the congruence subgroups of the modular group / P. Jaipong, W. Tapanyo // Algebra and Discrete Mathematics. — 2019. — Vol. 27, № 1. — С. 20–36. — Бібліогр.: 14 назв. — англ. |
| work_keys_str_mv |
AT jaipongp generalizedclassesofsuborbitalgraphsforthecongruencesubgroupsofthemodulargroup AT tapanyow generalizedclassesofsuborbitalgraphsforthecongruencesubgroupsofthemodulargroup |
| first_indexed |
2025-11-25T22:45:20Z |
| last_indexed |
2025-11-25T22:45:20Z |
| _version_ |
1850571092809220096 |
| fulltext |
“adm-n1” — 2019/3/22 — 12:03 — page 20 — #28
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 27 (2019). Number 1, pp. 20–36
c© Journal “Algebra and Discrete Mathematics”
Generalized classes of suborbital graphs
for the congruence subgroups
of the modular group
Pradthana Jaipong and Wanchai Tapanyo∗
Communicated by L. A. Kurdachenko
Abstract. Let Γ be the modular group. We extend a non-
trivial Γ-invariant equivalence relation on Q̂ to a general relation by
replacing the group Γ0(n) by ΓK(n), and determine the suborbital
graph FK
u,n, an extended concept of the graph Fu,n. We investigate
several properties of the graph, such as, connectivity, forest condi-
tions, and the relation between circuits of the graph and elliptic
elements of the group ΓK(n). We also provide the discussion on
suborbital graphs for conjugate subgroups of Γ.
Introduction
Let G be a permutation group acting transitively on a nonempty set X.
Then the action of G can be extended naturally on X ×X by
g(v, w) = (g(v), g(w)),
where g ∈ G and v, w ∈ X. The orbit G(v, w) is called a suborbital of
G containing (v, w). A suborbital graph G(v, w) for G on the set X is a
graph whose vertex set is the set X and the family of directed edges is
∗Corresponding author.
2010 MSC: Primary 05C20, 05C40, 05C63; Secondary 05C05, 05C60, 20H05.
Key words and phrases: modular group, congruence subgroups, suborbital
graphs.
“adm-n1” — 2019/3/22 — 12:03 — page 21 — #29
P. Jaipong, W. Tapanyo 21
the suborbital G(v, w). Hence, there exists a directed edge from v1 to v2,
denoted by v1 → v2, if (v1, v2) ∈ G(v, w).
The concept of suborbital graphs was first introduced by Sims [14].
Then Jones, Singerman, and Wicks [8] used this idea to construct the
suborbital graphs Gu,n for the modular group Γ acting on the extended set
of rational numbers Q̂ = Q∪{∞}. To examine the properties of Gu,n, they
applied the fact that the action of Γ on Q̂ is imprimitive, i.e., there is a
Γ-invariant equivalence relation other than the two trivial relations which
form the partitions {Q̂} and {{v} : v ∈ Q̂}. They used the congruence
subgroup Γ0(n) to induce the nontrivial Γ-invariant equivalence relation
on Q̂, and studied the subgraphs Fu,n of the graphs Gu,n restricted on
the block [∞], the equivalence class containing ∞. Note that the graph
Gu,n is the union of m copies of Fu,n, where m is the index of Γ0(n) in Γ.
Moreover, if Fu,n contains edges, it is actually a suborbital graph for Γ0(n)
on the block [∞].
There are several studies related to the graphs for the modular group,
see [1,4,5, 7, 11,13], and other papers about suborbital graphs for other
groups, see [2, 3, 6, 9, 10, 12]. In [11], the authors used the different Γ-
invariant equivalence relation obtained from another congruence subgroup
Γ1(n) of Γ, and investigated the connectivity of subgraphs of Gu,n on the
block containing ∞.
Inspired by the results in [8,11], we introduce a Γ-invariant equivalence
relation using the congruence subgroup ΓK(n) where K is a subgroup of
the group of unit Z∗
n. This group is a generalization of Γ0(n) and Γ1(n), so
it provides a generalized Γ-invariant equivalence relation of those induced
from Γ0(n) and Γ1(n). We denote by FK
u,n the subgraph of Gu,n on the
block [∞]K with respect to the group ΓK(n), and demonstrate various
properties of FK
u,n, such as, connectivity, forest conditions, including the
relation between circuits of the graph and elliptic elements of the group
ΓK(n). In the final section we provide a discussion of the relation of
suborbital graphs for congruence subgroups. We show that the suborbital
graphs for the group Γ0(n) studied in [7] is isomorphic to some graph
Fu,n. The result is also extended to the case of ΓK(n) and ΓK(n), a
generalization of Γ0(n). Moreover, we discuss suborbital graphs for ΓK(n)
on [∞]K which are more general than FK
u,n.
This work can be restricted to the case of Γ1(n) be replacing the
group K by the trivial subgroup {1} of Z∗
n. This case was studied in [11]
already; however, the results in there are different from ours because of
“adm-n1” — 2019/3/22 — 12:03 — page 22 — #30
22 Generalized classes of suborbital graphs
the definition of Γ1(n). The differences will be explained in another our
publication.
1. Preliminaries
Let Γ be a set of all linear fractional (Möbius) transformations on the
upper half-plane H2 = {z ∈ C : Im(z) > 0} of the form
z 7→
az + b
cz + d
, (1)
where a, b, c, d ∈ Z, and ad− bc = 1. With the composition of functions, Γ
forms a group which is called the modular group. The group Γ is isomorphic
to PSL(2,Z), the quotient group of the unimodular group SL(2,Z) by its
centre {±I}. Thus, every element of Γ of the form (1) can be referred to
as the pair of matrices
±
(
a b
c d
)
∈ SL(2,Z).
For convenience, we may leave the sign of matrices representing elements
of the group Γ and identify them with their negative sign.
Let n be any natural number. One can show that
Λ(n) =
{(
a b
c d
)
∈ SL(2,Z) : a ≡ 1 mod n, and b ≡ c ≡ 0 mod n
}
is a subgroup of SL(2,Z). The image of Λ(n) in Γ = PSL(2,Z) under the
quotient mapping is called the principal congruence subgroup of level n
and denoted by Γ(n). We can see easily that
Γ(n) =
{(
a b
c d
)
∈ Γ : a ≡ ±1 mod n, and b ≡ c ≡ 0 mod n
}
.
A subgroup of Γ containing Γ(n), for some n, is called a congruence
subgroup of Γ. There are two well-known congruence subgroups of the
modular group, that is,
Γ0(n) =
{(
a b
c d
)
∈ Γ : c ≡ 0 mod n
}
,
and
Γ1(n) =
{(
a b
c d
)
∈ Γ : a ≡ ±1 mod n, and c ≡ 0 mod n
}
.
“adm-n1” — 2019/3/22 — 12:03 — page 23 — #31
P. Jaipong, W. Tapanyo 23
These two groups are mainly used in [8] and [11], respectively.
We now introduce some classes of congruence subgroups of the modular
group. Let K be a subgroup of a group of units Z∗
n, and an denote a
congruence class containing an integer a modulo n. Without the confusion,
we may leave the subscript n and use a instead. One can prove easily that
ΛK(n) =
{(
a b
c d
)
∈ SL(2,Z) : a ∈ K, and c ≡ 0 mod n
}
is a subgroup of SL(2,Z) containing the group Λ(n), so the image in Γ of
this group is certainly a congruence subgroup of Γ. We let ΓK(n) denote
the congruence subgroup of Γ obtained in this way. Obviously,
ΓK(n) =
{(
a b
c d
)
∈ Γ : a ∈ −K ∪K, and c ≡ 0 mod n
}
,
where −K = {−a : a ∈ K}. In the case that K is a trivial subgroup of
Z∗
n, {1} or Z∗
n, ΓK(n) is such Γ1(n) and Γ0(n), respectively.
We see that every coefficient of a transformation in the modular group
is an integer. Then the action (1) can be extended to act on Q̂ = Q∪{∞}.
In [8], the authors represented every element in Q̂ as reduced fractions
x
y = −x
−y , where x, y ∈ Z and gcd(x, y) = 1. In the case of ∞, it is
represented by the fractions 1
0 = −1
0 . Now the action (1) of Γ on Q̂ can
be rewritten as follows,
x
y
7→
ax+ by
cx+ dy
.
Certainly, ax+by
cx+dy is a reduced fraction. The action of Γ on Q̂ is absolutely
independent from the non-uniqueness of the representations of fractions.
Note that the action of Γ on the set Q̂ is transitive, that is, for every
v, w ∈ Q̂ there exists a transformation γ ∈ Γ such that γ(v) = w,
equivalently, for every v ∈ Q̂ there exists γ ∈ Γ such that γ(∞) = v. This
means that we can represent every element in Q̂ by γ(∞), where γ ∈ Γ.
We see that Γ∞ < ΓK(n) 6 Γ where Γ∞ is the stabilizer of ∞, the set
of all translations z → z + b with b ∈ Z. The second inequality is strict if
n > 1. Then a nontrivial Γ-invariant equivalence relation on Q̂, see also
[8, page 319] for a general definition, related to the group ΓK(n) is given
by
γ(∞) ∼ γ′(∞) if and only if γ′ ∈ γΓK(n),
where γΓK(n) is a left coset of ΓK(n) in Γ. An equivalence class is called
a block and denoted by [v]K , the block containing an element v of Q̂.
“adm-n1” — 2019/3/22 — 12:03 — page 24 — #32
24 Generalized classes of suborbital graphs
From the relation obtained above, we see that the block [γ(∞)]K is
the set
{γΓK(n)}(∞) = {γγ
K
(∞) : γ
K
∈ ΓK(n)}.
In particular, the block [∞]K is the ΓK(n)-orbit,
{ΓK(n)}(∞) = {γK(∞) : γ
K
∈ ΓK(n)}.
Therefore, ΓK(n) acts transitively on the block
[∞]K =
{
x
y
∈ Q̂ : x ∈ −K ∪K, y ≡ 0 mod n
}
.
Proposition 1. Let n,m be positive integers, K and K ′ be subgroups of
Z∗
n and Z∗
m, respectively. Then the following statements are equivalent,
1) ΓK(n) 6 ΓK′(m),
2) [∞]K ⊆ [∞]K′ ,
3) m | n and {k ∈ Z : kn ∈ −K ∪K} ⊆ {k ∈ Z : km ∈ −K ′ ∪K ′}.
Proof. 1) ⇒ 2) It is obvious from the fact that if H 6 G, the orbit H(x)
is always contained in the orbit G(x).
2) ⇒ 3) Suppose that [∞]K ⊆ [∞]K′ , and a ∈ {k ∈ Z : kn ∈ −K∪K}.
Then a
n ∈ [∞]K ⊆ [∞]K′ . This implies that m | n and am ∈ −K ′ ∪K ′,
that is, a ∈ {k ∈ Z : km ∈ −K ′ ∪K ′}.
3) ⇒ 1) Suppose that the conditions hold, and
(
a b
c d
)
belongs to ΓK(n).
Then an ∈ −K ∪ K and c ≡ 0 mod n. Since m | n, we have c ≡ 0
mod m. The remaining condition implies that am ∈ −K ′ ∪ K ′. Hence,(
a b
c d
)
∈ ΓK′(m).
2. The graph F
K
u,n
In this section we determine the graph FK
u,n and describe general
properties of the graph, for example, edge conditions and isomorphism
results. Let G(v, w) be a suborbital graph for Γ on Q̂. The directed graph
G(v, w) and its arrow reversed graph G(w, v) are called paired suborbital
graphs. In the case G(v, w) = G(w, v), the graphs become undirected, we
will call them self-paired. Since Γ acts transitively on the set Q̂, there is a
transformation γ ∈ Γ mapping v to ∞. Hence, a suborbital graphs G(v, w)
and G(∞, γ(w)) are identical. If γ(w) = u
n where u, n ∈ Z, n > 0 and
gcd(u, n) = 1, the graph will be simply denoted by Gu,n. This is a notation
traditionally used in [8] and the related research. In the case u
n = ∞, the
graph just contains loop at every vertex, and every vertex is not adjacent
“adm-n1” — 2019/3/22 — 12:03 — page 25 — #33
P. Jaipong, W. Tapanyo 25
to others. This is a trivial case of the suborbital graphs, and need not
be studied. We will consider only the nontrivial case, that is, u
n 6= ∞. In
this case we let all edges be complete geodesics in the upper half-plane
H2 joining between two vertices. We denote by FK
u,n the subgraph of Gu,n
whose vertex set is the block [∞]K . For the case ΓK(n) = Γ0(n), the graph
and the block will be simply denoted by Fu,n and [∞]0, respectively. The
remark below demonstrates a trivial result immediate from Proposition 1
and the definition of FK
u,n.
Remark 1. If K 6 K ′, then FK
u,n is a subgraph of FK′
u,n. In particular,
FK
u,n is a subgraph of Fu,n.
For n = 1, we obtain ΓK(n) = Γ and [∞]K = Q̂. Hence G1,1 = F1,1 =
FK
1,1. We call this graph the Farey graph. The following are some basic
results of suborbital graphs for Γ which were obtained in [8].
Lemma 1. Γ acts on vertices and edges of Gu,n transitively.
Lemma 2. Gu,n = Gu′,n′ if and only if n = n′ and u ≡ u′ mod n.
Lemma 3. Gu,n is self-paired if and only if u2 ≡ −1 mod n.
Lemma 4. No edges of F1,1 cross in H2.
Proposition 2. There is an edge r
s → x
y in Gu,n if and only if one of the
following conditions holds,
1) x ≡ ur mod n, y ≡ us mod n and ry − sx = n,
2) x ≡ −ur mod n, y ≡ −us mod n and ry − sx = −n.
Next we state the first result for the graph FK
u,n, the edge conditions.
Let us consider the fractions r
s and x
y in the previous proposition. If they
are in the block [∞]K , then s ≡ r ≡ 0 mod n, so s ≡ ±ur mod n. We
now have the following proposition immediately.
Proposition 3. There is an edge r
s → x
y in FK
u,n if and only if it satisfies
one of the following conditions,
1) x ≡ ur mod n and ry − sx = n,
2) x ≡ −ur mod n and ry − sx = −n.
Suppose that v → w is an edge of FK
u,n. Then there exists a transfor-
mation γ ∈ Γ such that γ(∞ → u
n) = v → w. Since v are in [∞]K , we can
see easily that γ ∈ ΓK(n), and so u
n = γ−1(w) ∈
(
ΓK(n)
)
(∞) = [∞]K .
This means that if FK
u,n contains edges, it also contains the vertex u
n . The
“adm-n1” — 2019/3/22 — 12:03 — page 26 — #34
26 Generalized classes of suborbital graphs
converse is also true that if u
n is a vertex of FK
u,n, the graph contains
edges including the edge ∞ → u
n . We conclude this fact in the following
corollary.
Corollary 1. FK
u,n contains edges if and only if u
n ∈ [∞]K , i.e., u ∈
−K ∪K.
We have known that ΓK(n) acts transitively on the vertex set of FK
u,n,
the block [∞]K . We will show that it also acts transitively on edges of
FK
u,n. We may suppose that the graph contains edges. Then Corollary 1
implies that u
n ∈ [∞]K . Thus, FK
u,n is really a suborbital graph for ΓK(n)
on the block [∞]K . We now obtain a trivial consequences coming from
[8, Proposition 3.1] that ΓK(n) acts transitively on edges of FK
u,n.
Corollary 2. ΓK(n) acts on vertices and edges of FK
u,n transitively.
The next corollary provides the sufficient and necessary conditions for
FK
u,n to be a self-paired suborbital graph for ΓK(n).
Corollary 3. FK
u,n is self-paired if and only if u ∈ K and u2 ≡ −1
mod n.
Proof. Suppose that FK
u,n is self-paired. By using Lemma 1, Gu,n is self-
paired. Then Lemma 3 implies that u2 ≡ −1 mod n, and so, u ∈ K if
and only if −u ∈ K. Since FK
u,n contains edges, Corollary 1 implies that
u ∈ −K ∪ K. If u ∈ −K, we have −u ∈ K, and so, u ∈ K. For the
converse, Lemma 3 implies that Gu,n is self-paired. By Corollary 1, FK
u,n
contains edges, so it is a self-paired suborbital graph on [∞]K .
Next we verify the isomorphism results for the graph FK
u,n. The first
one shows that the reflection of FK
u,n across the imaginary axis is another
suborbital graph FK
−u,n. For the second one, let us consider the case of
the graph Fu,n first. Suppose that n is a multiple of a positive integer m.
[8, Lemma 5.3 (ii)] shows that Fu,n is an isomorphic subgraph of Fu,m. We
know by Remark 1 that FK
u,n is a subgraph of Fu,n. Hence, FK
u,n becomes
an isomorphic subgraph of Fu,m. Certainly, the graph Fu,m may not be
smallest, so we can find the smaller graph FK′
u,m containing FK
u,n as an
isomorphic subgraph.
Let K ′ = {km : kn ∈ K}. It is not difficult to see that K ′ is closed
under the multiplication modulo m, so K ′ 6 Z∗
m. We use K ′ to obtain
the general version of [8, Lemma 5.3 (ii)]. We are now ready to prove the
proposition.
“adm-n1” — 2019/3/22 — 12:03 — page 27 — #35
P. Jaipong, W. Tapanyo 27
Proposition 4.
1) FK
u,n is isomorphic to FK
−u,n by the mapping v 7→ −v.
2) If m | n, then FK
u,n is an isomorphic subgraph of FK′′
u,m by the mapping
v 7→ nv
m , where K ′′ is a supergroup of K ′ = {km : kn ∈ K}. In
particular, FK
u,n is an isomorphic subgraph of FK′
u,m
Proof. 1) We can see easily that r
s ∈ [∞]K if and only if −r
s ∈ [∞]K .
Clearly, the mapping is bijective. We need to check that the mapping
is edge-preserving so that it is an isomorphism. Let r
s → x
y be an edge
in FK
u,n. Then by Proposition 3, x ≡ ±ur mod n and ry − sx = ±n.
This implies that −x ≡ ∓(−u)(−r) mod n and (−r)y − s(−x) = ∓n.
Therefore, −r
s → −x
y is an edge of FK
−u,n.
2) We will prove only the particular case, the general case will be
obtained directly after applying Remark 1 which implies that FK′
u,m is a
subgraph of FK′′
u,m. Let m | n, and v = r
sn be a vertex of FK
u,n, s ∈ Z. We
then have v 7→ nv
m = r
sm . Since gcd(r, sn) = 1 and m | n, gcd(r, sm) = 1.
Since rn ∈ −K ∪K, we have rm ∈ −K ′∪K ′. Thus, r
sm is a vertex of FK′
u,n.
The injective property is obvious, so we prove only the edge-preserving
property. Suppose that r
sn → x
yn be an edge of FK
u,n. Proposition 3 implies
that x ≡ ±ur mod n, and r(yn) − (sn)x = ±n. Since m | n, x ≡ ±ur
mod m. We see that ry − sx = ±1, so r(ym)− (sm)x = ±m. Therefore,
there is an edge r
sm → x
ym in FKm
u,n .
Corollary 4. No edges of FK
u,n cross in H2
Proof. By using the second result of Proposition 4 with m = 1, FK
u,n
becomes an isomorphic subgraph of F1,1. Lemma 4 said that there are no
edges of F1,1 crossing in H2. Then so does FK
u,n.
3. Connectivity of graphs
In this section we investigate connectivity of the graph FK
u,n. The goal
of this section is to show the following theorem.
Theorem 1. The graph FK
u,n is connected if and only if n 6 4.
To prove this theorem we consider each case of n. Proposition 5 and
Proposition 7 will result the conclusion when n 6 4 and n > 5, respectively.
Now let us consider the graph FK
u,n. We have known from Remark 1 that
FK
u,n is a subgraph of Fu,n. The connectivity of Fu,n was already concluded
“adm-n1” — 2019/3/22 — 12:03 — page 28 — #36
28 Generalized classes of suborbital graphs
in [8, Theorem 5.10]. However, results for the subgraph does not depend
on its supergraph in general. Thus, it is worth examining the connectivity
of FK
u,n. One can verify that FK
u,n = Fu,n if and only if −K ∪K = Z∗
n, that
is, ΓK(n) = Γ0(n). Then we prove only the case −K ∪K ⊂ Z∗
n. The cases
n 6 4 or n = 6 need not be proved since FK
u,n = Fu,n for every subgroup
K of Z∗
n. For completeness, we conclude them again in the proposition
below using the notation FK
u,n, and then prove the remaining cases.
Proposition 5. FK
u,6 is not connected, but FK
u,n is connected for every
n 6 4.
Lemma 5. Let j
k be a reduced fraction where k | n. Then there are not
adjacent vertices v and w of FK
u,n such that v < j
k < w.
Proof. We assume by contrary that v and w are adjacent vertices of FK
u,n.
By using Proposition 4 with m = 1, the vertices nv and nw are adjacent
in F1,1. Then the edge joining these two vertices crosses an edge nj
k → ∞
of F1,1 in H2 that provides a contradiction to Lemma 4. Thus, v and w
cannot be adjacent
Lemma 6. Let a, b, k ∈ Z, and b 6= 0 6= k. Then 1+2abk
4b2k
is a reduced
fraction.
Proof. Let p = gcd(1+2abk, 4b2k) and q = gcd(p, 2bk). Then q | 1+2abk
and q | 2bk. Thus q | 1, so q = 1. Hence, p = gcd(p, 4b2k) = 1.
Proposition 6. If n > 5, the graph FK
u,n with u ≡ ±1 mod n is not
connected.
Proof. The case n = 6 is concluded in Proposition 5. Then we suppose
that n 6= 6. By using Lemma 2 and Lemma 4, we can consider only the
case u = 1. We see that the block [∞]K always contains all fractions
r
s with r ≡ ±1 mod n and s ≡ 0 mod n. If the block [∞]K contains
another fraction x
y with x 6≡ ±1 mod n, by using Proposition 3, x
y is
never joined to r
s . This provides disconnectedness of the graph. Next we
suppose that the block [∞]K contains only fractions r
s where r ≡ ±1
mod n and s ≡ 0 mod n. Since n > 5 and n 6= 6, there are at least two
proper fractions z
n and z′
n such that 1
n < z
n < z′
n < n−1
n . We will show that
the interval ( zn ,
z′
n ) contains some vertices of FK
u,n. Certainly, every vertex
of the graph in this interval is not adjacent to ∞. By using Lemma 6 with
a = z + z′ and b = n, we obtain that 1+2(z+z′)nk
4n2k
is a reduced fraction.
Obviously, it is contained in [∞]K for every k ∈ N. If we consider this
“adm-n1” — 2019/3/22 — 12:03 — page 29 — #37
P. Jaipong, W. Tapanyo 29
fraction as an infinite sequence over the index k, the sequence converges
to the fraction z+z′
2n , the middle value of the open interval ( zn ,
z′
n ). Thus,
the interval contains vertices of FK
u,n. We now replace j
k in Lemma 5 by
z
n and z′
n . Hence, vertices of FK
u,n in the interval ( zn ,
z′
n ) is separated from
others outside the interval providing disconnectedness of the graph.
Lemma 7. If u 6≡ ±1 mod n, then there are not adjacent vertices v and
w of FK
u,n such that v < 1
2 < w.
Proof. The case that n is even follows from Lemma 5. We then suppose
that n is odd. Assume that v is adjacent to w. Then Lemma 4 implies that
nv and nw are adjacent vertices in F1,1. By using [8, Lemma 4.1], nv and
nw are adjacent term in some Fm, the Farey sequence of order m. Since
nv < n
2 < nw, we obtain m = 1. Then nv = (n−1)/2 and nw = (n+1)/2,
so v = (n−1)/2
n and w = (n+1)/2
n . If v → w is an edge in FK
u,n, Proposition
3 implies that (n+ 1)/2 ≡ −u(n− 1)/2 mod n. Then 1 ≡ −u(−1) ≡ u
mod n which contradicts to the assumption. For the case that w → v
is an edge of FK
u,n, we will obtain u ≡ −1 mod n. This also provides a
contradiction. Therefore, v and w are not adjacent in FK
u,n.
Proposition 7. FK
u,n is not connected for every n > 5.
Proof. In this proposition we prove the remaining cases. Here, we can
assume that −K ∪ K ⊂ Z∗
n and u 6≡ ±1 mod n. Since −K ∪ K ⊂ Z∗
n,
there exists t
n ∈ (0, 1) such that t
n /∈ [∞]K . By using Proposition 3,
one can compute that there are at most two vertices of FK
u,n in the
interval (0, 1) adjacent to ∞. Hence, there is at least one interval ( rs ,
x
y ),
where r
s ,
x
y ∈ {0, 12 ,
t
n , 1}, not containing these two vertices. We now put
a = ry + sx, b = sy, and apply Lemma 6 with the same step used in
Proposition 6. We finally obtain at least one vertex of FK
u,n contained
in ( rs ,
x
y ). Certainly, every vertex of FK
u,n in ( rs ,
x
y ) is not adjacent to ∞.
By applying Lemma 5, some cases may require Lemma 7, the vertices
in ( rs ,
x
y ) is not adjacent to other vertices this interval. Thus FK
u,n is not
connected.
4. Circuits of graphs
This section discusses circuits of the graph FK
u,n. A circuit of FK
u,n
is a sequence of m > 3 different vertices v1, v2, . . . , vm ∈ FK
u,n such that
v1 → v2 → · · · → vm → v1 and some arrows may be reversed. If m = 3,
“adm-n1” — 2019/3/22 — 12:03 — page 30 — #38
30 Generalized classes of suborbital graphs
we call it a triangle. A directed triangle is a triangle whose arrows are
in the same direction. Otherwise, called an anti-directed triangle. The
next two statements, Proposition 8 and Remark 2, provide sufficient and
necessary conditions for the graph FK
u,n to contain triangles.
Proposition 8. FK
u,n contains directed triangles if and only if u
n ∈ [∞]K
and u2 ± u+ 1 ≡ 0 mod n.
Proof. Let FK
u,n contains directed triangles. Then so does Fu,n since FK
u,n is
a subgraph Fu,n. By [8, Theorem 5.11] we have u2±u+1 ≡ 0 mod n. Since
FK
u,n contains edges, Corollary 1 implies that u
n ∈ [∞]K . For the converse
implication, we suppose that the conditions hold. Then u ∈ −K ∪ K.
Since u2 ± u + 1 ≡ 0 mod n, u± 1 = ∓u2 ∈ −K ∪K. We now obtain
u±1
n ∈ [∞]K . By Proposition 3, one can easily check that the graph FK
u,n
contains the directed triangle of the form ∞ → u
n → u±1
n → ∞.
It is not difficult to see that Fu,1 = F1,1 is a self-paired graph containing
directed triangles. Then, it contains anti-directed triangles. [8, Theorem
5.11 (ii)] said that Fu,n contains no anti-directed triangles if n > 1. Since
FK
u,n is a subgraph of Fu,n and they are identical if n = 1, it is worth to
remark that,
Remark 2. FK
u,n contains anti-directed triangles if and only if n = 1.
The next proposition was proved in [1, Theorem 10] for the case of
Fu,n that the graph is a forest, a graph contains no circuits, if and only if
it contains no triangles. The general case can be proved by using this fact
together with Proposition 8.
Theorem 2. FK
u,n is a forest if and only if it contains no triangles, i.e.,
u
n /∈ [∞]K or u2 ± u+ 1 6≡ 0 mod n.
Proof. The forward implication is clear by the definition of a forest. For
the converse we assume the contrary that FK
u,n contains circuits. Then so
does Fu,n. By the proof of [1, Theorem 10], Fu,n contains triangles. Thus,
we have u2 ± u+ 1 ≡ 0 mod n. Since there is an edge in FK
u,n, Corollary
1 implies that u
n ∈ [∞]K . By Proposition 8, FK
u,n contains triangles.
We know from Theorem 1 that FK
u,n is connected if and only if n 6 4.
Combine with Theorem 2, we obtain the following corollary.
Corollary 5. FK
u,n is a tree if and only if n = 2, 4.
“adm-n1” — 2019/3/22 — 12:03 — page 31 — #39
P. Jaipong, W. Tapanyo 31
In Section 2 we have proved that ΓK(n) acts transitively on vertices
and edges of FK
u,n, see Corollary 2. This situation also occurs for directed
triangles. The proof can be done by using the transitivity of the action of
ΓK(n) on edges of FK
u,n.
Proposition 9. ΓK(n) acts on directed triangles of FK
u,n transitively.
Proof. By Proposition 8, we see that if FK
u,n contains triangles, it always
contains the triangle 1
0 → u
n → u±1
n → 1
0 . Suppose that v1 → v2 → v3 →
v1 is an arbitrary directed triangle in FK
u,n. It is sufficient to show that
there is a transformation γ ∈ ΓK(n) such that γ(∞ → u
n → u±1
n → ∞) =
v1 → v2 → v3 → v1.
Since v1 → v2 is an edge of the graph FK
u,n, Corollary 2 implies that
there is an element γ ∈ ΓK(n) such that γ(∞ → u
n) = v1 → v2. One can
verify that γ is unique. Next we prove γ(u±1
n ) = v3. Since v3 → v1 and
v2 → v3 are edges of FK
u,n, we obtain that γ−1(v3 → v1) = γ−1(v3) → ∞
and γ−1(v2 → v3) =
u
n → γ−1(v3) are edges of FK
u,n. First, we apply edge
conditions, Proposition 3, to the first identity and obtain γ−1(v3) =
x
n
for some x ∈ Z. Next we replace γ−1(v3) in the second identity by x
n and
apply Proposition 3 again. Then un− xn = ±n, and so x = u± 1. Thus,
γ(u±1
n ) = v3. The proof is now complete.
In the proof of the previous proposition, the triangle v1 → v2 → v3 →
v1 is arbitrary. If we replace v1, v2 and v3 by u
n ,
u±1
n and ∞, respectively,
then there is a unique transformation γ1 ∈ ΓK(n) rotating the triangle
∞ → u
n → u±1
n → ∞ in such a way that γ1(∞ → u
n → u±1
n → ∞) = u
n →
u±1
n → ∞ → u
n . One can show easily that
γ1 =
(
u −(u2 ± u+ 1)/n
n −(u± 1)
)
.
Therefore, γ1 and γ in the proof above induce a unique transformation
γγ1γ
−1 rotating another given directed triangle in FK
u,n. We provide the
lemma below after concluding this result with more precisely.
Lemma 8. Let γ =
(
a b
c d
)
is an elliptic element of the modular group Γ,
that is |a + d| < 2. if |a + d| = 0, then γ has order 2, otherwise, γ has
order 3.
Proof. Suppose that |a+ d| = 0. Then γ =
(
a b
c −a
)
, so −a2 − bc = 1. We
see that
γ2 =
(
a2 + bc ab− ab
ac− ac a2 + bc
)
=
(
−1 0
0 −1
)
“adm-n1” — 2019/3/22 — 12:03 — page 32 — #40
32 Generalized classes of suborbital graphs
becomes the identity transformation. Hence, γ has order 2.
Next suppose that |a+ d| = 1. Then d = −(a± 1). We will prove only
the case d = −a− 1. The other case can be proved similarly. Now we have
γ =
(
a b
c −a−1
)
and −a2 − a− bc = 1. Consider
γ2 =
(
a2 + bc ab− ab− b
ac− ac− c a2 + 2a+ 1 + bc
)
=
(
−a− 1 −b
−c a
)
.
We see that γ2 is the inverse transformation of γ. Then γ has order 3.
Remark 3. Elements of Γ which are conjugate to elliptic elements are
elliptic, so γγ1γ
−1 is elliptic.
Corollary 6. There is a unique elliptic element γ of order 3 in ΓK(n)
rotating a triangle v1 → v2 → v3 → v1 of FK
u,n in such a way that
γ(v1 → v2 → v3 → v1) = v2 → v3 → v1 → v2.
The above corollary and the two consequences below are all about
relations between elliptic elements in the group ΓK(n) and its suborbital
graph FK
u,n. All of them were proved already in [1] for the version of Γ0(n)
and Fu,n. The proofs of the two results below follow from the former.
Theorem 3. ΓK(n) contains an elliptic element of order 3 if and only if
there exists u ∈ −K ∪K such that FK
u,n contains a triangle.
Proof. Suppose that
γ =
(
a b
c d
)
is an elliptic element of order 3 contained in ΓK(n). Then Lemma 8 implies
that |a+ d| = 1. Since γ ∈ ΓK(n), ad ≡ 1 mod n. Thus a2 ± a+ 1 ≡ 0
mod n. Certainly, a ∈ −K ∪ K. If we choose u ≡ a mod n, Theorem
8 implies that FK
u,n contains a triangle. Conversely, suppose that the
conditions hold. Again, by using Theorem 8, we obtain u2 ± u + 1 ≡ 0
mod n. Now let γ be the transformation
γ1 =
(
u −(u2 ± u+ 1)/n
n −(u± 1)
)
defined before Lemma 8. It is certainly an elliptic element of order 3 in
ΓK(n).
Theorem 4. ΓK(n) contains an elliptic element of order 2 if and only if
there exists u ∈ K such that FK
u,n is self-paired.
“adm-n1” — 2019/3/22 — 12:03 — page 33 — #41
P. Jaipong, W. Tapanyo 33
Proof. Suppose that
γ =
(
a b
c d
)
is an elliptic element of order 2 contained in ΓK(n). Then Lemma 8 implies
that a+ d = 0. Since γ ∈ ΓK(n), ad ≡ 1 mod n. Then a2 ≡ −1 mod n.
Certainly, a ∈ −K ∪K. If a ∈ K, we choose u ≡ a mod n. If a ∈ −K,
we choose u ≡ −a mod n. Thus, we have u ∈ K and u2 ≡ −1 mod n.
Now apply Corollary 3, we obtain that FK
u,n is self-paired. Conversely,
suppose that the conditions hold. Again, by using Corollary 3, we obtain
u2 ≡ −1 mod n, that is, u2 + 1 ≡ 0 mod n. Hence by computation, the
transformation (
u −(u2 + 1)/n
n −u
)
belongs to ΓK(n). Lemma 8 implies that it is an elliptic element of
order 2.
5. Graphs for conjugate subgroups of Γ
This section is inspired by [5,7] which studied suborbital graphs for
the groups Γ0(n) and Γ0(n), respectively. As subgroups of the modular
group Γ, they are considered to act on Q̂, and their specific suborbital
graphs were determined on their orbits whom they act transitively. We
extend the topic to the case of ΓK(n) and ΓK(n). The discussion shows
that we can study only the suborbital graph FK
u,n to conclude some general
properties of a suborbital graph for ΓK(n) through a graph isomorphism.
We start with the spacial case of the groups Γ0(n) and Γ0(n). The
group Γ0(n) is another congruence subgroup of Γ determined by,
Γ0(n) =
{(
a b
c d
)
∈ Γ : b ≡ 0 mod n
}
.
It is conjugate to the group Γ0(n). More precisely, Γ0(n) = γΓ0(n)γ
−1
where γ =
(
0 −1
1 0
)
∈ Γ. In [5], the authors determined the suborbital
graphs of Γ0(n) on its orbit containing ∞,
(
Γ0(n)
)
(∞) = {x
y ∈ Q̂ : y ≡ 0
mod n}. They assumed and studied for the case that n is a prime number
p. Suborbital graphs whom they studied are, in fact, the graph Fu,p on
the block [∞]0. Likewise, in [7], the authors studied suborbital graphs
for Γ0(p). In this case the graphs were determined on the orbit of 0,(
Γ0(p)
)
(0) = {x
y ∈ Q̂ : x ≡ 0 mod p}. We shall roughly denote it by
“adm-n1” — 2019/3/22 — 12:03 — page 34 — #42
34 Generalized classes of suborbital graphs
F̄p,u, the suborbital graph for Γ0(p) whose edges from the suborbital(
Γ0(p)
)
(0, p
u). What is the relation between the graphs Fu,p and F̄p,u?
We see that
(
Γ0(p)
)
(0, p
u) =
(
γΓ0(n)
)
(∞, −u
p ). Then F̄p,u is actually a
subgraph of G−u,p on the block [0]0 = [γ(∞)]0. It is certainly isomorphic
to the graph F−u,p, and so, isomorphic to the graph Fu,p after applying
Proposition 4. This fact can be directly extended to the case of ΓK(n)
and ΓK(n) where ΓK(n) is a congruence subgroup of Γ defined by
ΓK(n) =
{(
a b
c d
)
∈ Γ : a ∈ −K ∪K, and b ≡ 0 mod n
}
.
Certainly, Γ0(n) = γΓ0(n)γ
−1. We let F̄K
n,u denote the suborbital graph for
ΓK(n) on the orbit
(
ΓK(n)
)
(0) = [0]K where the suborbital
(
ΓK(p)
)
(0, nu )
is the set of edges.
Proposition 10. FK
u,n, F
K
−u,n, F̄
K
n,u and F̄K
n,−u are isomorphic.
Next we discuss the more general suborbital graph for ΓK(n) on [∞]K .
We have known that if FK
u,n contains edges, it is certainly a suborbital
graph for ΓK(n). However, not all suborbital graphs for ΓK(n) can be
represented by some FK′
u,m. We need to introduce some notations before
clarifying this claim by a trivial example on Γ0(2).
Notation. We denote by FK
n (∞, v) the suborbital graph for ΓK(n) on
[∞]K whose edges from the suborbital
(
ΓK(n)
)
(∞, v), and denote by
F̄K
n (0, v) the suborbital graph for ΓK(n) on [0]K whose edges from the
suborbital
(
ΓK(n)
)
(0, v). For the case of Γ0(n) and Γ0(n) we will leave
the letter K for the notation of graphs and replace K by 0 for the notation
of blocks.
Let us consider the block [∞]0 of the group Γ0(2). It certainly contains
the fraction 1
4 . We show that F2(∞, 14) cannot be written as the graph
FK
u,n for some u
n ∈ Q̂, and some K 6 Z∗
n. If F2(∞, 14) = FK
u,n, then
1
4 ∈ [∞]K , and so n | 4. Thus n = 1, 2, 4. It is obvious that n 6= 1 and
n 6= 4 because they provide vertex sets which are larger and smaller than
[∞]0, respectively. For the remaining case, it is clear that F2(∞, 14) 6= F1,2
since F1,2 does not contain the edge ∞ → 1
4 . Surely, the same situation
occurs on the graphs for ΓK(n). However, we see that FK
n (∞, u
m) and
F̄K
n (0,−m
u ) are subgraphs of Gu,m restricted on the blocks [∞]K and [0]K ,
respectively. Then the following result is still true.
Proposition 11. FK
n (∞, u
m) and F̄K
n (0,−m
u ) are isomorphic.
“adm-n1” — 2019/3/22 — 12:03 — page 35 — #43
P. Jaipong, W. Tapanyo 35
We have shown that some suborbital graph for ΓK(n) on the block
[∞]K can not be written as FK′
u,m. However, the graph is, in fact, the
disjoint union of copies of some graph FK′
u,m. This is the reason why we can
study only the graph which is represented by FK
u,n to obtain the results
for this general case.
Let us consider the graph FK
n (∞, u
m). Certainly, n | m and un ∈
−K ∪K. We may assume that un ∈ K, and define K ′ = 〈um〉, the cyclic
subgroup of Z∗
m generated by um. One can verify easily that the union of all
congruence classes in K ′ is a subset of the union of those congruence classes
in K. Thus, Proposition 1 implies that ΓK′(m) 6 ΓK(n). We now have
ΓK(n)∞ < ΓK′(m) 6 ΓK(n), where ΓK(n)∞ is the stabilizer subgroup of
ΓK(n) fixing ∞. Similar to the case of Γ and its congruence subgroup,
this provides the ΓK(n)-invariant equivalence relation on the block [∞]K
related to ΓK′(m), and the partition
{(
γΓK′(m)
)
(∞) : γ ∈ ΓK(n)
}
on
[∞]K is formed. We see that the orbit
(
ΓK′(m)
)
(∞) is, in fact, the block
[∞]K′ and the restriction of the graph FK(∞, u
m) on [∞]K′ is actually
the graph FK′
u,m. Therefore F(∞, u
m) is the disjoint union of j copies
of the graph FK′
u,m where j = |ΓK′(m) : ΓK(n)|, the index of ΓK′(m)
in ΓK(n). Since FK′
u,m and FK′
−u,m are isomorphic, then F(∞, u
m) and
F(∞, −u
m ) are isomorphic. After applying this result together with the
previous proposition, we now have the following consequences immediately.
Theorem 5. FK(∞, u
m), FK(∞,− u
m), F̄K(0, mu ), F̄
K(0,−m
u ) are iso-
morphic.
Corollary 7. F(∞, u
m), F(∞,− u
m), F̄(0, mu ), F̄(0,−m
u ) are isomorphic.
Acknowledgement
This research was supported by Chiang Mai University.
References
[1] M. Akbas. On suborbital graphs for the modular group, Bull. London Math. Soc.,
Vol. 33, N. 6, 2001, pp. 647–652.
[2] Mehmet Akbaş, Tuncay Kör, Yavuz Kesicioğlu. Disconnectedness of the subgraph
F
3 for the group Γ3, J. Inequal. Appl., Vol. 2013:283, 2013.
[3] Murat Beşenk, Bahadır Ö. Güler, Ali H. Değer, Yavuz Kesicioğlu. Circuit lengths
of graphs for the Picard group, J. Inequal. Appl., Vol. 2013:106, 2013.
[4] Ali H. Değer, Murat Beşenk, Bahadır Ö. Güler, On suborbital graphs and related
continued fractions, Appl. Math. Comput., Vol. 218, N. 3, 2011, pp.746–750.
“adm-n1” — 2019/3/22 — 12:03 — page 36 — #44
36 Generalized classes of suborbital graphs
[5] Bahadir O. Guler, Serkan Kader, Murat Besenk, On suborbital graphs of the
congruence subgroup Γ0(N), Int. J. Comput. Math. Sci., Vol. 2, N. 3, 2008, pp.
153–156.
[6] Bahadır Ö. Güler, Murat Beşenk, Yavuz Kesicioğlu, Ali Hikmet Değer, Suborbital
graphs for the group Γ2, Hacettepe Journal of Mathematics and Statistics, Vol.
44, N. 5, 2015, pp. 1033–1044.
[7] Bahadır Ö. Güler, Serkan Kader, On the action of Γ0(N) on Q̂, Note Mat., Vol.
30, N. 2, 2010, pp. 141–148.
[8] G. A. Jones, D. Singerman, K. Wicks, The modular group and generalized Farey
graphs, Groups–St. Andrews 1989, Vol. 2, London Math. Soc. Lecture Note Ser.,
160, Cambridge Univ. Press, Cambridge, 1991, pp. 316–338.
[9] Serkan Kader, Bahadır Ö. Güler, On suborbital graphs for the extended modular
group Γ̂, Graphs Combin., Vol. 29, N. 6, 2013, pp. 1813–1825.
[10] I. N. Kamuti, E. B. Inyangala, J. K. Rimberia, Action of Γ∞ on Z and the
corresponding suborbital graphs, Int. Math. Forum, Vol. 7, N. 30, 2012, pp. 1483–
1490.
[11] Yavuz Kesicioğlu, Mehmet Akbaş, Murat Beşenk. Connectedness of a suborbital
graph for congruence subgroups, J. Inequal. Appl., Vol. 2013:117, 2013.
[12] Refik Keskin, On suborbital graphs for some Hecke groups, Discrete Math., Vol.
234, 2001, pp. 53–64.
[13] R. Sarma, S. Kushwaha, R. Krishnan, Continued fractions arising from F1,2, J.
Number Theory, Vol. 154, 2015, pp. 179–200.
[14] Charles C. Sims. Graphs and finite permutation groups, Mathematische Zeitschrift,
Vol. 95, N. 1, 1967, pp. 76–86.
Contact information
Pradthana Jaipong Research Center in Mathematics and
Applied Mathematics,
Department of Mathematics,
Faculty of Science, Chiang Mai University,
Chiang Mai, 50200, Thailand
E-Mail(s): pradthana.j@cmu.ac.th
Wanchai Tapanyo Division of Mathematics and Statistics,
Faculty of Science and Technology,
Nakhon Sawan Rajabhat University,
Nakhon Sawan, 60000, Thailand
E-Mail(s): wanchai.t@nsru.ac.th
Received by the editors: 13.10.2016.
|