# Counting of Distinct Equivalence Classes of Circuits inPSL2,Z-Space

Authors: Hanan Alolaiyan; Muhammad Aamir; Awais Yousaf; Abdul Razaq
Journal: Journal of Mathematics
 (2022)

---

## Abstract

Graham Higman was the first who studied the transitive actions of the extended modular groupPGL2,Z over PLFq=Fq∪∞ graphically and named it as coset diagram. In these sorts of graphs, a closed path of edges and triangles is known as a circuit. Coset diagrams evolve through the joining of these circuits. In a coset diagram, a circuit is termed as a length-l circuit if its one vertex is fixed by x1x2π1x1x2−1π2x1x2π3,…,x1x2−1πl∈PSL2,Z, and it is denoted by π1,π2,π3,…,πl. In this study, we shall formulate combinatorial sequences and find the number of distinct equivalence classes of a length-6 circuit π1,π2,π3,π4,π5,π6 for a fixed number of triangle Δ of class Π.


---

## Body

## 1. Introduction

Consider,ℍ=p+iq;p,q∈ℝ,q>0, the model of the upper-half plane of the hyperbolic plane geometry, also known as the Lobachevski plane model. Then, M, the group of Mobius transformations [1], λ⟶aλ+b/cλ+d with a,b,c,d∈ℝ and ad−bc=±1, is the group of isometries that preserve the orientation in ℍ. It is isomorphic to the quotient group PSL2,ℝ, which is called the projective special linear group. Geometrically, the group of isometries of ℍ is the action of PSL2,ℝ on ℍ [2] with left action (faithful) as(1)abcdλ=aλ+bcλ+d⋅The Mobius transformations ofℍ with coefficients from the set of integers form a group known as a discrete group [3], a subgroup of PSL2,ℝ, symbolically written as PSL2,Z. It is a quotient group of the special linear group SL2,Z, by its center I,−I.It is prominent that the transformations of linear fractionsx1:λ⟶−1/λ and x2:λ⟶λ−1/λ are used to generate PSL2,Z, so-called the modular group, with(2)<x1,x2;x12=x23=1>⋅By introducing a new generatorx3:λ⟶1/λ with x1 and x2, we obtain a group PGL2,Z, the extension of PSL2,Z, using(3)x12=x23=x32=x1x32=x2x32=1,as a relation [4–6]. In 1978, Professor Graham Higman propounds an unfamiliar type of graph, said to be a coset diagram, which presents the action of PGL2,Z on PLFq, the projective line over the finite field Fq, where q shows the prime power. In 1983, this foundation is laid by Mushtaq [7]. Small triangles are proposed for the cycles x23, such that x2 permutes the vertices of triangles in the anticlockwise direction, and an edge is attached to any two vertices that are interchanged by x1. Heavy dots represent the fixed point of x1 and x2. Note that x2x32=1 equals x3x2x3=x2−1, that means x3 reverses the triangle orientation proposed for the cycle x23. For that reason, the diagram need not be made more intricate by inserting x3 edges. Coset diagrams have some attractive stories for the action of PSL2,Z on real quadratic fields. The number E¯=x−√ϵ/a is called the conjugate of E=x+√ϵ/a, where x and a are the integers and ϵ is the fixed number from Z+, which is not a perfect square. E is said to be an ambiguous number if E and E¯ are opposite in signs. E is said to be totally negative (positive) if E and E¯ both have the same signs. For a fixed value of ϵ, there is only a finite number of ambiguous numbers of the form E=x+√ϵ/a and that component of the coset diagram made by the ambiguous numbers forms a closed path (circuit), and it is the only closed path in E orbit [8–10].A closed path of triangles and edges in a coset diagram for the action onPLFq by the modular group is called a circuit [11, 12]. For a coset diagram, a circuit is termed as a length-l circuit if its one vertex is fixed by x1x2π1x1x2−1π2x1x2π3,…,x1x2−1πl∈PSL2,Z, and it is denoted by π1,π2,π3,…,πl.Alternatively, it means that one vertex ofπ1 triangles lies outside of the circuit, and one vertex of the π2 triangles lies inside of the circuit and likewise. Since π1,π2,π3,…,πl is a cycle, so it does not matter if one vertex of π1 triangles lies inside of the circuit and one vertex of the π2 triangles lies outside of the circuit and likewise. Note that l is always even.Remark 1.
Consider a circuit of length-6π1,π2,π3,π4,π5,π6 (Figure 1). Then, the circuits in the following are proposed as the same.(4)π1,π2,π3,π4,π5,π6,π2,π3,π4,π5,π6,π1,π3,π4,π5,π6,π1,π2,π4,π5,π6,π1,π2,π3π5,π6,π1,π2,π3,π4,π6,π1,π2,π3,π4,π5,π6,π5,π4,π3,π2,π1,π5,π4,π3,π2,π1,π6π4,π3,π2,π1,π6,π5,π3,π2,π1,π6,π5,π4,π2,π1,π6,π5,π4,π3,π1,π6,π5,π4,π3,π2.
Except these 12, it is obvious from Figure1 that there are no more representations for length-6 circuits.Figure 1
Circuit of length-6.


## 2. Objective

The equation(5)π1+π2+π3+⋯+πr=p,has p−1r−1 number of solutions in positive integer [13]. So, there are Δ−15 solutions to the equation(6)π1+π2+π3+π4+π5+π6=Δ,in natural numbers. Every such solution gives a circuit π1,π2,π3,π4,π5,π6 implying total Δ−15 number of length-6 circuits with Δ triangles. But out of Δ−15, there are certain length-6 circuits, which are the same. Our objective is to find a number of distinct solutions.Fragments are used for the composition of these diagrams, and circuits are used for the composition of fragments. There are many articles on finding the number of circuits in different types of graphs [14–18]. In this study, we answer the question, for a given Δ, how many distinct equivalence classes are found, for the class(7)π1≠π2≠π3≠π4,of the circuit π1,π2,π3,π4,π5,π6 with the vertical axis of symmetry that is π2=π6,π3=π5.Definition 1.
If the circuitsπ1,π2,π3,π4,π5,π6 and π1′,π2′,π3′,π4′,π5′,π6′ are the same, then they said to be equivalent, and we denote this equivalency as(8)π1,π2,π3,π4,π5,π6≈π1′,π2′,π3′,π4′,π5′,π6′.
Letk¯=kifk=0,6kmod6otherwise, we make a result as follows.Remark 2.
π1,π2,π3,π4,π5,π6 ≈π1′,π2′,π3′,π4′,π5′,π6′ if and only if for some fix i∈0,1,2,3,4,5, and for all j=1,2,3,4,5,6, one of the following is true.(9)iπj′=πi+j¯,iiπj′=π7−i−j¯.
SupposeΠ is the set, containing all length-6 circuits π1,π2,π3,π4,π5,π6 of the class π1≠π2≠π3≠π4 with π2=π6,π3=π5. Then, it is quite apparent that each equivalence class π1,π2,π3,π4,π5,π6∈Π contains a maximum of 6 circuits that are equivalent as follows:(10)π1,π2,π3,π4,π5,π6,π2,π3,π4,π5,π6,π1,π3,π4,π5,π6,π1,π2π4,π5,π6,π1,π2,π3,π5,π6,π1,π2,π3,π4,π6,π1,π2,π3,π4,π5,due to the vertical axis of symmetry.
Let us label the number of distinct equivalence classes ofΠ by NΠ. Then, we start with the following theorem.Theorem 1.
NΠ is equal to the cardinality of(11)Θ=2γ,2ξ,δ,ϑ:2γ+2ξ+δ+ϑ=Δ;γ,ξ∈Z+;γ≠ξ;δ,ϑ∈Z+\γ,ξ;δ<ϑ;γ+ξ,δ+ϑ∈Z+\1,2⋅Proof.
We define a set as(12)Ξ=θ,τ:θ+τ=Δ;θ∈Z+\1,2;τ∈2Z+\2,4.
Now, for eachθ,τ∈Ξ, make a set as follows:(13)Ωθ,τ=θ,2γ,2ξ:2γ+2ξ=ϑ;γ,ξ∈Z+;γ≠ξ.
For eachθ,2γ,2ξ∈Ωθ,τ, make another set as follows:(14)Γθ,2γ,2ξ=δ,ϑ:δ+ϑ=θ;δ,ϑ∈Z+\γ,ξ;δ<ϑ.
Then, there is a quadruple2γ,2ξ,δ,ϑ, for each θ,2γ,2ξ∈Ωθ,τ and δ,ϑ∈Γθ,2γ,2ξ, which further produces a circuit π1,π2,π3,π4,π5,π6 with the following demonstration:(15)π1=δ,π2=γ,π3=ξ,π4=ϑ,π5=ξ,π6=γ.
Consider2γ,2ξ,δ,ϑ; then, the following four cases emerge.(1)
If we consider any two, three, or all elements ofγ,ξ,δ,ϑ are same, then the resulting circuit does not belong to Π. Suppose δ<ϑ and γ<ξ.(2)
If we interchangeδ and ϑ, then the resulting quadruple 2γ,2ξ,ϑ,δ gives the circuit ϑ,γ,ξ,δ,ξ,γ in Π, which is not equivalent to the circuit δ,γ,ξ,ϑ,ξ,γ generated by 2γ,2ξ,δ,ϑ.(3)
If we interchangeγ and ξ, then the resulting quadruple 2ξ,2γ,δ,ϑ gives the circuit δ,ξ,γ,ϑ,γ,ξ, which is not equivalent to the circuit δ,γ,ξ,ϑ,ξ,γ generated by 2γ,2ξ,δ,ϑ.(4)
If we interchangeγ and ξ and also δ and ϑ, then the resulting quadruple 2ξ,2γ,ϑ,δ gives the circuit ϑ,ξ,γ,δ,γ,ξ in Π, which is equivalent to the circuit δ,γ,ξ,ϑ,ξ,γ generated by 2γ,2ξ,δ,ϑ.
Therefore, in order to produce distinct circuits, we consider either (i)γ≠ξ,δ<ϑ or (ii) δ≠ϑ,γ<ξ. Without loss of generality, we choose condition (i).
Hence,NΠ, the number of distinct circuits of class Π, is equal to the cardinality of(16)Θ=2γ,2ξ,δ,ϑ:2γ+2ξ+δ+ϑ=Δ;γ,ξ∈Z+;γ≠ξ;δ,ϑ∈Z+\γ,ξ;δ<ϑ;γ+ξ,δ+ϑ∈Z+\1,2⋅
So, to findNΠ, we have to calculate the cardinality of Θ. For this, we let(17)χ=4,ifΔ≡0mod2,3,otherwise,be the smallest of θ.
For eachθ,τ∈Ξ, define a superset of Ωθ,τ as(18)Ωθ,τ′=θ,2γ,2ξ:2γ+2ξ=ϑ;γ,ξ∈Z+,and for each θ,2γ,2ξ∈Ωθ,τ′, we define a superset of Γθ,2γ,2ξ as(19)Γθ,2γ,2ξ′=δ,ϑ:δ+ϑ=θ;δ,ϑ∈Z+;δ<ϑ.
This implies that(20)Γθ,2γ,2ξ′\Γθ,2γ,2ξ=δ,ϑ:δ+ϑ=θ;δ∈γ,ξ\ϑ;ϑ∈γ,ξ\δ;δ<ϑ.
Since,θ+τ=Δ implies θ+2γ+2ξ=Δ⟹3+2γ+2≤Δ gives γ≤Δ−5/2. Thus, γ∈1,2,…,Δ−5/2. Similarly, ξ∈1,2,…,Δ−5/2.
There are tripletsθ,2γ,2ξ∈Ωθ,τ', where γ=ξ. Now, we find those values of γ, where γ=ξ. As we know that θ+τ=Δ implies 3+τ≤Δ⟹τ≤Δ−3 implies 2γ+2ξ≤Δ−3 gives 4γ≤Δ−3, and hence, γ≤Δ−3/4. This implies that γ∈1,2,…,Δ−3/4.
Now, the structure ofΘ shows that(21)Θ=∑γ=1Δ−5/2∑k=χΔ−2γ−2Γk,2γ,Δ−k−2γ′−Γk,2γ,Δ−k−2γ′\Γk,2γ,Δ−k−2γ−∑γ=1Δ−3/4ΓΔ−4γ,2γ,2γ′−ΓΔ−4γ,2γ,2γ′\ΓΔ−4γ,2γ,2γ.
It is easy to prove thatΓθ,2γ,2ξ′=θ−1/2. This implies that(22)∑γ=1Δ−5/2∑k=χΔ−2γ−2Γk,2γ,Δ−k−2γ′=∑γ=1Δ−5/2χ−12+χ+12+⋯+Δ−3−2γ2=∑γ=1Δ−5/21+2+3+⋯+Δ−3−2γ2=∑γ=1Δ−5/2Δ−3−2γ/2Δ−1−2γ/22, (23)∑γ=1Δ−3/4ΓΔ−4γ,2γ,2γ′=∑γ=1Δ−3/4Δ−4γ−12.
Now, we have to find(24)∑γ=1Δ−5/2∑k=χΔ−2γ−2Γk,2γ,Δ−k−2γ′\Γk,2γ,Δ−k−2γand∑γ=1Δ−3/4ΓΔ−4γ,2γ,2γ′\ΓΔ−4γ,2γ,2γ.
For this, we partitionΩθ,τ′ into three subsets in the following definitions.Definition 2.
For a fixedγ, the triplet θ,2γ,2ξ∈Ωθ,τ′ is said to be yellow if and only if θ≤ξ.Definition 3.
For a fixedγ, the triplet θ,2γ,2ξ∈Ωθ,τ′ is said to be pink if and only if θ=2ξ.Definition 4.
For a fixedγ, the triplet θ,2γ,2ξ∈Ωθ,τ′ is said to be black if and only if θ>ξ and θ≠2ξ.Lemma 1.
For allγ, if B is the number of black triplets in Ωθ,τ′, then(25)∑γ=1Δ−5/2∑k=χΔ−2γ−2Γk,2γ,Δ−k−2γ′\Γk,2γ,Δ−k−2γ=2B−Δ−66,ifΔ≡0mod6,B−Δ−36,ifΔ≡3mod6,B,otherwise.Proof.
Letθ,2γ,2ξ∈Ωθ,τ′ be a black triplet, that is, θ>ξ and θ≠2ξ. Then, ∃ a pair δ,ϑ=θ−ξ,ξ,ifθ−ξ<ξξ,θ−ξ,ifξ<θ−ξ∈Γθ,2γ,2ξ′ but does not belong to Γθ,2γ,2ξ, implying that δ,ϑ∈Γθ,2γ,2ξ′\Γθ,2γ,2ξ.
Now, ifθ,2γ,2ξ is a yellow or pink triplet, then it is absolutely insignificant that Γθ,2γ,2ξ′ does not contain any pair δ,ϑ, such that either δ=ξ or ϑ=ξ. We will make Definitions 2–4 for a fix ξ and repeat the same procedure.
There are tripletsθ,2γ,2ξ∈Ωθ,τ′, where either γ=δ,ξ=ϑ or γ=ϑ,ξ=δ. Here, δ+ϑ=γ+ξ⟹2θ=τ⟹3θ=θ+τ⟹θ=Δ/3 implies Δ≡0mod3.
Now, we find number of such triplets. Since,θ=Δ/3 implies τ=2Δ/3⟹2γ+2ξ=2Δ/3 gives 2+2ξ≤2Δ/3⟹ξ≤Δ−3/3. This implies that ξ∈1,2,…,Δ−3/3. So, the total number of such triplets is Δ−3/3. These all triplets are pink and black because(26)ξ=Δ3−γ≤Δ3=θ.
It is quite obvious that the number of such pink triplets is(27)1,ifΔ≡0mod6,0,otherwise,θ=2ξ⟹2ξ=Δ/3 implies ξ=Δ/6⟹Δ=0mod6.
Thus, the number of black triplets inΩθ,τ′ for the condition either γ=δ,ξ=ϑ or γ=ϑ,ξ=δ is(28)Δ−63,ifΔ≡0mod6,Δ−33,ifΔ≡3mod6,0,otherwise.
These black triplets are considered only once, either for allγ or for all ξ. Hence,(29)∑γ=1Δ−5/2∑k=χΔ−2γ−2Γk,2γ,Δ−k−2γ′\Γk,2γ,Δ−k−2γ=2B−Δ−66,ifΔ≡0mod6,B−Δ−36,ifΔ≡3mod6,B,otherwise.Lemma 2.
For allγ=ξ, if B′ is the number of black triplets in Ωθ,τ′, then(30)∑γ=1Δ−3/4ΓΔ−4γ,2γ,2γ′\ΓΔ−4γ,2γ,2γ=2B′.Proof.
Letθ,2γ,2γ∈Ωθ,τ′ be a black triplet, that is θ>γ and θ≠2γ. Then, ∃ a pair δ,ϑ=θ−γ,γifθ−γ<γγ,θ−γifγ<θ−γ∈Γθ,2γ,2γ′ but does not belong to Γθ,2γ,2γ, implying that δ,ϑ∈Γθ,2γ,2γ′\Γθ,2γ,2γ.
Now, ifθ,2γ,2γ is a yellow or pink triplet, then it is absolutely insignificant that Γθ,2γ,2γ′ does not contain any pair δ,ϑ, such that either δ=γ or ϑ=γ. We will make Definitions 2–4 for a fix ξ and repeat the same procedure. Hence,(31)∑γ=1Δ−3/4ΓΔ−4γ,2γ,2γ′\ΓΔ−4γ,2γ,2γ=2B′.
Now, we find the value ofB in the next lemma.Lemma 3.
(32)B=∑γ=1Δ−5/2Δ−2γ3−1−Δ−64,ifΔ≡0mod2,∑γ=1Δ−5/2Δ−2γ3−1,otherwise.Proof.
Letθ,2γ,2ξ∈Ωθ,τ′ be a yellow triplet, that is, θ≤ξ; then, 3≤θ≤ξ⟹3≤Δ−2γ−2ξ≤ξ implying that Δ−2γ/3≤ξ≤Δ−3−2γ/2. Thus, ξ∈Δ−2γ/3,Δ−2γ/3+1,…,Δ−3−2γ/2. Therefore, ξ has Δ−3−2γ/2−Δ−2γ/3+1 values, which shows that for a fix γ, the number of yellow triplets in Ωθ,τ′ is Δ−3−2γ/2−Δ−2γ/3+1. For all γ, let Y be number of yellow triplets in Ωθ,τ′; then,(33)Y=∑γ=1Δ−5/2Δ−3−2γ2−Δ−2γ3+1.
It is easy to prove that for a fixγ, the number of pink triplets Ωθ,τ′ is 1,ifΔ≡2γmod4,0,otherwise.
For allγ, let P be the number of pink triplets in Ωθ,τ′; then,(34)P=Δ−84,ifΔ≡0mod4,Δ−64,ifΔ≡2mod4,0,otherwise.=Δ−64,ifΔ≡0mod2,0,otherwise.
For a fixγ, let Ωθ,τγ be the cardinality of Ωθ,τ′; then, Ωθ,τγ=Δ−3−2γ/2. This implies that(35)B=∑γ=1Δ−5/2Ωθ,τγ−Y−P.
Substituting the value ofY and P in the above equation, we get(36)B=∑γ=1Δ−5/2Δ−2γ3−1−Δ−64,ifΔ≡0mod2,∑γ=1Δ−5/2Δ−2γ3−1,otherwise.
In the following lemma, we calculate the value ofB′.Lemma 4.
(37)B′=Δ−15−1,ifΔ≡0mod6,Δ−15,otherwise.Proof.
θ>ξ⟹θ−1≥ξ implies ξ≤Δ−τ−1⟹ξ≤Δ−1/5. This implies that ξ∈1,2,…,Δ−1/5. Since, the condition θ>ξ contains the condition θ=2ξ. So, for all γ=ξ, Δ−1/5 are the total numbers of black and pink triplets. It is quite obvious that for all γ=ξ,
Total number of pink triplet =1,ifΔ≡0mod20,otherwise
This implies that(38)B′=Δ−15−1,ifΔ≡0mod6,Δ−15,otherwise.
Now, we prove our main result in the following theorem.Theorem 5.
ForΔ>12(39)NΠ=∑γ=1Δ−5/2Δ−3−2γ/2Δ−1−2γ/22−∑γ=1Δ−3/4Δ−4γ−12−2∑γ=1Δ−5/2Δ−2γ3−1−Δ−64−Δ−15−Δ−66+1,ifΔ≡0mod6,∑γ=1Δ−5/2Δ−2γ3−1−Δ−15,ifΔ≡±1mod6,∑γ=1Δ−5/2Δ−2γ3−1−Δ−64−Δ−15,ifΔ≡±2mod6,∑γ=1Δ−5/2Δ−2γ3−1−Δ−15−Δ−36,otherwise.Proof.
Since,NΠ is equal to the cardinality of Θ. So, we find Θ.
Substituting the values ofB and B′ in equations (25) and (30), respectively, we get(40)∑γ=1Δ−5/2∑k=χΔ−2γ−2Γk,2γ,Δ−k−2γ′\Γk,2γ,Δ−k−2γ=2∑γ=1Δ−5/2Δ−2γ3−1−Δ−64−Δ−66,ifΔ≡0mod6,∑γ=1Δ−5/2Δ−2γ3−1,ifΔ≡±1mod6,∑γ=1Δ−5/2Δ−2γ3−1−Δ−64,ifΔ≡±2mod6,∑γ=1Δ−5/2Δ−2γ3−1−Δ−36,otherwise,(41)∑γ=1Δ−3/4ΓΔ−4γ,2γ,2γ′\ΓΔ−4γ,2γ,2γ=Δ−15−1,ifΔ≡0mod6,Δ−15,otherwise.
Substitution of equations (22), (23), (40), and (41) in equation (21) gives the value of Θ, which further proves the theorem.
IfΔ=13, then there are 2 distinct equivalence classes of the circuit Π, and these are(42)3,1,2,4,2,1,3,2,1,4,1,2.
IfΔ=14, then there are 4 distinct equivalence classes of the circuit Π, and these are(43)3,1,2,5,2,1,3,2,1,5,1,2,2,1,3,4,3,1,2,3,1,4,1,3.
IfΔ=15, then there are 10 distinct equivalence classes of the circuit Π, and these are(44)3,1,2,6,2,1,3,2,1,6,1,2,4,1,2,5,2,1,4,2,1,5,1,2,2,1,3,5,3,12,3,1,5,1,3,2,1,4,3,4,1,2,4,1,3,1,4,1,2,3,4,3,2,1,3,2,4,2,3.
IfΔ=16, then there are 10 distinct equivalence classes of the circuit Π, and these are(45)3,1,2,7,2,1,3,2,1,7,1,2,4,1,2,6,2,1,4,2,1,6,1,2,2,1,3,6,3,12,3,1,6,1,3,1,2,3,5,3,2,1,3,2,5,2,3,1,2,4,3,4,2,1,4,2,3,2,4.
IfΔ=17, then there are 18 distinct equivalence classes of the circuit Π, and these are(46)3,1,2,8,2,1,3,2,1,8,1,2,4,1,2,7,2,1,4,2,1,7,1,2,5,1,2,6,2,1,5,2,1,6,1,22,1,3,7,3,1,2,3,1,7,1,3,4,1,3,5,3,1,4,3,1,5,1,3,2,1,4,5,4,1,2,4,1,5,1,42,1,5,3,5,1,2,5,1,3,1,5,1,2,3,6,3,2,1,3,2,6,2,3,1,3,4,2,4,3,1,4,3,2,3,4.
IfΔ=18, then there are 22 distinct equivalence classes for the circuit Π, and these are(47)3,1,2,9,2,1,3,2,1,9,1,2,4,1,2,8,2,1,4,2,1,8,1,2,5,1,2,7,2,1,5,2,1,7,1,22,1,3,8,3,1,2,3,1,8,1,3,4,1,3,6,3,1,4,3,1,6,1,3,2,1,4,6,4,1,2,4,1,6,1,43,1,4,5,4,1,3,4,1,5,1,4,2,1,5,4,5,1,2,5,1,4,1,5,1,2,3,7,3,2,1,3,2,7,2,31,2,4,5,4,2,1,4,2,5,2,4,1,2,5,3,5,2,1,5,2,3,2,5.
Now, if we substitute all these values ofΔ in Theorem 2.11 in their respective cases, we get the same cardinality of Π as above, that is, 2,4,10,10,18, and 22, respectively, and so on; for any value of Δ, we can find the number of distinct equivalence classes of Π.


## 3. Conclusion

The result which is proved in this study not only provides the number of distinct equivalence classes for the classΠ of length-6 circuits in the coset diagrams but also gives a number of solutions to the linear equation 2i+2j+x+y=Δ with i≠j≠x≠y and x<y, from the set of natural numbers. The result is also true if we replace n-gons at the place of triangles in length-6 circuits for class Π.



---

*Source: 4863429-2022-04-09.xml*