Graphs and Combinatorics (2017) 33:1531–1542 DOI 10.1007/s00373-017-1852-x ORIGINAL PAPER

Circuits in Suborbital Graphs for The Normalizer Serkan Kader1

Received: 12 April 2017 / Revised: 19 September 2017 / Published online: 12 October 2017 © Springer Japan KK 2017

Abstract In this paper, we investigate suborbital graph for the normalizer of Γ0 (N ) in P S L(2, R), where N will be of the form 22 3 p 2 , p is prime number greater than 3 and p ≡ 1 (mod 3) . Then we give edge and circuit conditions on graphs arising from the imprimitive action of the normalizer. Keywords Normalizer · Suborbital graph · Imprimitive action · Circuit Mathematics Subject Classification 11F06 · 20H10 · 05C20 · 05C25

1 Introduction Let P S L(2, R) denote the group of all linear fractional transformations T : z −→

az + b , where a, b, c, d are real and ad − bc = 1. cz + d

This is the automorphism group of the upper half plane U := {z ∈ C : Im(z) > 0} . Γ , the modular group, is the subgroup of P S L(2, R) such that a, b, c and d are integers. Γ0 (N ) is the subgroup of Γ with N |c. In terms of matrix representation, the elements of P S L(2, R) correspond to the matrices   ab ± , a, b, c, d ∈ R and ad − bc = 1. cd

B 1

Serkan Kader [email protected] Department of Mathematics, Faculty of Arts and Sciences, Ni˘gde Ömer Halisdemir University, Ni˘gde, Turkey

123

1532

Graphs and Combinatorics (2017) 33:1531–1542

The normalizer of Γ0 (N ) in P S L(2, R) is studied by Lehner and Newman in [11]. Lehner and Newman calculated the normalizer directly. But, the exact characterization of the elements of the normalizer N or (N ) of Γ0 (N ) in connection with the Monster simple group was given by Conway and Norton in [5], as following form; 

ae b/ h cN / h de

 ,

(1.1)

where all symbols represent integers, h is the largest divisor of 24 for which h 2 |N , e > 0 is an exact divisor of hN2 [(that is r is an exact divisor of s, denoted by r  s, if r | s and (r, rs ) = 1] and the determinant of matrix is e. The suborbital graph for the normalizer of Γ0 (N ) in P S L(2, R) was studied in [3,9,10], when N is square-free positive integer. Also for some special cases in which N is not square-free, all circuits in suborbital graph was obtained in [6–8]. In this study N will be of the form 22 3 p 2 , where p is prime number greater than 3.

2 The Action of N or(22 3 p2 ) on A Maximal Set ˆ = Q ∪ {∞} can be represented as a Every element of the extended set of rationals Q x reduced fraction , with x, y ∈ Z and (x, y) = 1. ∞ is represented as 01 = −1 0 . The y   x ab action of the matrix on is cd y 

ab cd

 :

x ax + by → . y cx + dy

Lemma 2.1 ([2]) Let N be any integer and has the prime power decomposition ˆ if and only if α1 ≤ 7, α1 ≤ 3 2α1 ·3α2 · p3α3 · · · prαr . Then N or (Γ0 (N )) is transitive on Q

and αi ≤ 1 for i = 3, . . . , r. ˆ Corollary 2.2 The action of the normalizer N or (22 3 p 2 ) is not transitive on Q. Proof Since α3 = 2, the result is clear by Lemma 2.1.



ˆ on which the normalizer acts transitively. Now, we must find maximal subset of Q From this action, we will give edge and circuit conditions on suborbital graphs. For this, we give some results helping us. Lemma 2.3 ([3]) Given an arbitrary rational number ks ∈ Q with (k,s)=1, then there  k   k1  = with s1 |N .

exists an element A ∈ Γ0 (N ) such that A s s1 Lemma 2.4 ([3]) Let d|N and (a1 , d) = (a2 , d) = 1. Then under Γ0 (N ) if and only if a1 ≡ a2 (mod t), where t = (d, From Lemma 2.3 and Lemma 2.4, we get;

123

a1 a2 d and d N d ).

are conjugate



Graphs and Combinatorics (2017) 33:1531–1542

1533

  a a under Γ0 (N ) is the set Lemma 2.5 ([6]) Let d|N . Then the orbit of d d    N y x ˆ . Furthermore, the number of orbits y ∈ Q : (N , y) = d, a ≡ x d mod d, d   a

with d|N under Γ0 (N ) is just ϕ(d, Nd ), where ϕ is Euler function. d ˆ are Corollary 2.6 The orbits of the action of Γ0 (22 3 p 2 ) on Q                       1 1 1 1 1 1 1 1 1 1 1 ; ; ; 2 ; ; 2 ; 2 ; ; ; ; ; p 1 2 3 2 2·3 2 3 2 p2 3 p2 22 p 2 2 · 3 p2                 1 1 2 p−1 1 p+2 3 2p − 1 ; , ,..., ; , , ,..., ; 22 3 p 2 p p p 2p 2p 2p 2p                 1 2 p+3 2p − 1 1 p+2 3 2p − 1 , , ,..., ; , , 2 ..., ; 3p 3p 3p 3p 22 p 22 p 2 p 22 p             b p−1 a1 a2 a p−1 b1 b2 , ,..., ; , 2 ,..., 2 , 2 2 · 3p 2 · 3p 2 · 3p 2 3p 2 3p 2 3p

where ai ≡ a j (mod p) and bi ≡ b j (mod p), and the number of orbits is 6 p + 6.   a Proof For the orbit , the possible values of d are 1, 2, 3, 22 , 2 · 3, 22 3, p, 2 p, 3 p, d 22 p, 2 · 3 p, 22 3 p, p 2 , 2 p 2 , 3 p 2 , 22 p 2 , 2 · 3 p 2 , 22 3 p 2 by Lemma 2.3. Thus, the number of non-conjugate classes of these orbits using Euler’s formula are 1 and p-1 for 1, 2, 3, 22 , 2 · 3, 22 3, p 2 , 2 p 2 , 3 p 2 , 22 p 2 , 2 · 3 p 2 , 22 3 p 2 and p, 2 p, 3 p, 22 p, 2 ·

3 p, 22 3 p respectively. The results is obvious by Lemma 2.4. Now, we determine elements of N or (22 3 p 2 ). From (1.1), h = 2 and e = 1, 3, p 2 or 3 p 2 . Hence, we get    b b a 3a 2 2 , det T1 = 1, T2 = , det T2 = 3, T1 = 2 · 3 p2 c d 2 · 3 p 2 c 3d     b b ap 2 3ap 2 2 2 2 , det T , det T4 = 3 p 2 . T3 = = p , T = 3 4 2 · 3 p 2 c dp 2 2 · 3 p 2 c 3dp 2 

ˆ on which the normalizer N or (22 3 p 2 ) acts Theorem 2.7 The maximal subset of Q transitively is               1 1 1 ˆ 2 3 p2 ) = 1 ∪ 1 ∪ 1 ∪ 1 ∪ ∪ 2 ∪ ∪ Q(2 2·3 2 3 p2 1 2 3 22           1 1 1 1 1 ∪ ∪ ∪ ∪ . ∪ 3 p2 22 p 2 2 · 3 p2 22 3 p 2 p2

123

1534

Graphs and Combinatorics (2017) 33:1531–1542

  1 Proof We just examine the action of the elements of N or (22 3 p 2 ) on the orbit . 1   b a 2 , ad − 3bcp 2 = 1. Then Firstly, we consider the element T1 = 2 2 · 3p c d 

b a 2 2 2 · 3p c d

    1 2a + b . = 1 2(2 · 3 p 2 c + d)

Hence, using Lemma 2.5, we have following cases

  2a + b 1 (1*) If a is even, b, c and d are odd and 3  d, then ∈ . 2 2(2· 3p c + d) 2  1 1 (2*) If a and d are even, b and c are odd, and 3  d, T1 ∈ 2 . 1 2     1 1 ∈ . Similarly, for the (3*) If a and d are odd, b is even and 3  d, then T1 1 1     b 3a 2 3 p 2 ), 3ad − bcp 2 = 1, from T 1 , 2 element T2 = ∈ N or (2 2 2 · 3 p 2 c 3d 1       1 1 1 we get the orbits , and 2 . 3 2·3 2 3       1 1 1 2 2 Moreover, for T3 , T4 ∈ N or (2 3 p ), the orbits , , 2 and 2 2 2 2p p 2 p       1 1 1 , , 2 2 are obtained respectively. 3 p2 2 · 3 p2 2 3p



ˆ 2 3 p 2 ) is an infinite cyclic group. Lemma 2.8 The stabilizer of a point in Q(2 ˆ 2 3 p 2 ) are conjugate. Hence, Proof By Theorem 2.7, the stabilizers of two points in Q(2 it is sufficient to consider the stabilizers of ∞ in N or (22 3 p 2 ). Since T

         b ae 1 1 1 ae 2 = , = = 2 2 0 0 0 2 · 3p c 2 · 3 p c de 

we get c = 0 and e = 1. Furthermore, by determinant, ad = 1. So T =  1  1 2 . This shows that N or∞ (22 3 p 2 ) = 01

1 b2 01

 .



ˆ 2 3 p 2 ), We now consider the imprimitivity of the action of N or (22 3 p 2 ) on Q(2 beginning with a general discussion of primitivity of permutation groups. Let (G, ) be a transitive permutation group, consisting of a group G acting on a set transitively. An equivalence relation ≈ on is called G-invariant if, whenever α, β ∈ satisfy α ≈ β, then g(α) ≈ g(β) for all g ∈ G. The equivalence classes are called blocks, and the block containing α is denoted by [α].

123

Graphs and Combinatorics (2017) 33:1531–1542

1535

We call (G, ) imprimitive if admits some G-invariant equivalence relation different from 1. the identity relation, α ≈ β if and only if α = β; 2. the universal relation, α ≈ β for all α, β ∈ . Otherwise (G, ) is called primitive. These two relations are supposed to be trivial relations. Clearly, a primitive group must be transitive, for if not the orbits would form a system of blocks. The converse is false, but we have the following useful result. Lemma 2.9 ([4]) Let (G, ) be a transitive permutation group. (G, ) is primitive if and only if G α , the stabilizer of α ∈ , is a maximal subgroup of G for each α ∈ .

From Lemma 2.9, we see that whenever, for some α, G α  H  G, then admits some G-invariant equivalence relation other than the trivial cases. Because of the transitivity, every element of has the form g(α) for some g ∈ G. Thus one of the non-trivial G-invariant equivalence relation on is given as follows: g(α) ≈ g  (α) if and only if g  ∈ g H.

(2.1)

The number of blocks is the index |G : H | and the block containing α is just the orbit H (α). ˆ 2 3 p 2 ), To apply these ideas to the case where G is the N or (22 3 p 2 ), and is Q(2 we take      b b a 3a 2 ,T = 2 . N0 (22 3 p 2 ) = Γ0 (22 3 p 2 ), T1 = 2 2 · 3 p2 c d 2 · 3 p 2 c 3d and N or∞ (22 3 p 2 ) instead of H and G α . Clearly N or∞ (22 3 p 2 ) < N0 (22 3 p 2 ) < N or (22 3 p 2 ). Here, we aim is to investigate the structure of N or (22 3 p 2 ) by approximating the normalizer with the elements of N0 (22 3 p 2 ) and also is to characterize the elements of N0 (22 3 p 2 ) with graphs. Lemma 2.10 ([1]) The index of Γ0 (N ) in N or (N ) is given by



N or (N ) : Γ0 (N ) = 2ρ h 2 τ, where ρ is the number of prime factors of N / h 2 , τ = ( 23 )ε1 ( 43 )ε2 ,  ε1 =

1, if 22 , 24 , 26  N ; and ε2 = 0, otherwise



1, if 9  N ; 0, otherwise.



123

1536

Graphs and Combinatorics (2017) 33:1531–1542

Theorem 2.11 The blocks arising from the imprimitive action as follows:             1 1 1 1 1 1 ∪ 2 , ∪ ∪ ∪ 2 ∪ 2·3 2 3 1 2 3 2             (2.2) 1 1 1 1 1 1 [∞] := ∪ ∪ ∪ ∪ ∪ . p2 2 p2 3 p2 22 p 2 2 · 3 p2 22 3 p 2 [0] :=

Proof By Lemma 2.10, h = 2, ρ = 2, τ = 23 for N = 22 3 p 2 . So, N or (22 3 p 2 ) :

Γ0 (22 3 p 2 ) = 22 · 22 · 23 = 24. Since T12 ∈ Γ0 (22 3 p 2 ) ⇔ a + d ≡ 0 (mod 2) and T16 = I ⇔ a + d = ±1, N0 (22 3 p 2 ) : Γ0 (22 3 p 2 ) = 12. If we use the equation







N or (22 3 p 2 ) : Γ0 (22 3 p 2 ) = N or (22 3 p 2 ) : N0 (22 3 p 2 ) · N0 (22 3 p 2 ) : Γ0 (22 3 p 2 ) ,



we get N or (22 3 p 2 ) : N0 (22 3 p 2 ) = 2.   b 1 1 3ap 2 2 Now, we show that 2 ≈ p2 . If we take g1 = , g2 = 2 · 3 p 2 3dp 2   b      6a 2 ∈ N or (22 3 p 2 ), then g1 01 = p12 , g2 01 = 21 . But, since 2 2 · 3 p 3d g2 g1−1



ab 2 6ad − bc 2 − ab p = 2 2 · 3cd( p − 1) 3ad − bc

by the relation (2.1), we obtain are found as in (2.2).

1 2

≈

 ∈ / N0 (22 3 p 2 ),

1 p 2 . With similar calculations, the blocks



ˆ 2 3 p2 ) 3 Suborbital Graphs of N or(22 3 p2 ) on Q(2 The idea of the suborbital graphs of a permutation group G acting on a set is introduced by Sims in [12]. These are graphs with vertex-set , on which G induces automorphisms. We summarise Sims’ theory as follows: Let (G, ) be transitive permutation group. Then G acts on × by g(α, β) = (g(α), g(β)), (g ∈ G, α, β ∈ ). The orbits of this action are called suborbitals of G. The orbit containing (α, β) is denoted by O(α, β). From O(α, β) we can form a suborbital graph G(α, β) : its vertices are the elements of , and there is a directed edge from γ to δ if (γ , δ) ∈ O(α, β). A directed edge from γ to δ is denoted by γ → δ. Shortly, there exists an edge γ → δ in G(α, β) if and only if there is g ∈ G such that g(α) = γ and g(β) = δ . So we can draw this edge as a hyperbolic geodesic in the upper half-plane U , that is, as Euclidean semi-circles or half-lines perpendicular to real line. The orbit O(β, α) is also a suborbital graph and it is either equal to or disjoint from O(α, β). In the latter case G(β, α) is just G(α, β) with the arrows reserved and we call, in this case, G(α, β) and G(β, α) paired suborbital graphs. In the former case G(α, β) = G(β, α) and the graph consists of pairs of oppositely directed edges; it is

123

Graphs and Combinatorics (2017) 33:1531–1542

1537

convenient to replace each such pair by a single undirected edge, so that we have an undirected graph which we call self paired. If α = β, then O(α, α) = {(γ , γ ) | γ ∈ } is the diagonal of × . The corresponding suborbital graph G(α, α), called the trivial suborbital graph, is selfpaired: it consists of a loop based at each vertex γ ∈ . ˆ 2 3 p 2 ). We now determine the suborbital graphs for the action N or (22 3 p 2 ) on Q(2 2 2 2 2 2 2 ˆ Since the action N or (2 3 p ) on Q(2 3 p ) is transitive, N or (2 3 p ) permutes the blocks transitively; so the subgraphs are all isomorphic. Thus it is sufficient to study with only one block. On the other hand, it is clear that each non-trivial suborbital graph  ˆ 2 3 p 2 ), where (u, p 2 ) = 1. Therefore, we contains a pair ∞, pu2 for some pu2 ∈ Q(2     work on the following case: We denote by F ∞, pu2 the subgraph of G ∞, pu2 whose vertices are in the block             1 1 1 1 1 1 [∞] = ∪ ∪ ∪ 2 2 ∪ ∪ 2 2 , p2 2 p2 3 p2 2 p 2 · 3 p2 2 3p  so that G ∞,

u p2



 consists of two disjoint copies F ∞,

Theorem 3.1 Let rs and   F ∞, pu2 if and only if

x y

u p2

 .

be in the block [∞]. Then there is an edge

r s

→

x y

in

1. If 22 3 p 2 s, then x ≡ ±ur (mod p 2 ), y ≡ ±us (mod p 2 ), r y − sx = ± p 2 , 2. If 2 · 3 p 2 s, then x ≡ ±2ur (mod p 2 ), y ≡ ±2us (mod p 2 ), r y − sx = ±2 p 2 , 3. If 22 p 2 s, then x ≡ ±3ur (mod p 2 ), y ≡ ±3us (mod p 2 ), r y − sx = ± p 2 , 4. If 3 p 2 s, then x ≡ ±4ur (mod p 2 ), y ≡ ±4us (mod p 2 ), r y − sx = ± p 2 , 5. If 2 p 2 s, then x ≡ ±6ur (mod p 2 ), y ≡ ±6us (mod p 2 ), r y − sx = ±2 p 2 , 6. If p 2 s, then x ≡ ±12ur (mod p 2 ), y ≡ ±12us (mod p 2 ), r y − sx = ± p 2 .   > → xy be an edge in F ∞, pu2 . Then there is an element T = Proof Let rs −   b   ae 2 ∈ N or (22 3 p 2 ) such that T (∞) = rs and T pu2 = xy . Now, sup2 · 3 p 2 c de   b a 2 , ad − 3bcp 2 = 1, pose that 22 3 p 2 s. So T must be of the form T1 = 2 · 3 p2 c d where a and d are odd, b and c are even and 3  a. From 

a b0 T1 (∞) = 2 2 2 3 p c0 d

  1 a r = 2 2 = , 0 2 3 p c0 s

we get r = a and s = 22 3 p 2 c0 . Also  T1

u p2



 =

a b0 22 3 p 2 c0 d



u p2

 =

au + b0 p 2 x = , 2 + dp y

22 3 p 2 c0 u

123

1538

Graphs and Combinatorics (2017) 33:1531–1542

gives that x = au + b0 p 2 and y = 22 3 p 2 c0 u + dp 2 . That is, x ≡ ur (mod p 2 ) and y ≡ us (mod p 2 ). Since 

a b0 22 3 p 2 c0 d



1 u 0 p2



 =

a au + b0 p 2 2 2 2 2 3 p c0 2 3 p 2 c0 u + dp 2

 =

  r x , s y

we have r y − sx = p 2 . This proves (1). For T1 , if the following conditions hold, then (2) and (4) are obtained; • a, b and c are odd, d is even and 3  a, and • a and d are even, b and c are  odd and b3  a, respectively. 3a 2 Now, we take the element T2 = , 3ad − bcp 2 = 1. If a, b and c are 2 · 3 p 2 c 3d odd, d is even and 3  b, then from 

b 3a 2 T2 (∞) = 2 · 3 p 2 c 3d

  a r 1 = = , 2 0 2p c s

we obtain r = a and s = 2 p 2 c, that is 2 p 2 s. Furthermore  T2

u p2



 =

b 3a 2 2 2 · 3 p c 3d



u p2

 =

6au + bp 2 x = . 6(2 p 2 cu + dp 2 ) y



  3a b2 Since the matrix has determinant 1 and (u, p 2 ) = 1, then 6au + p2 c d    bp 2 , 2(2 p 2 cu + dp 2 ) = 1. Therefore 6au + bp 2 , 6(2 p 2 cu + dp 2 ) = 1. Hence we get x ≡ 6ur (mod p 2 ) and y ≡ 6us (mod p 2 ). As 

b 3a 2 2 2 · 3 p c 3d



1 u 0 p2



 =

   a 6au + bp 2 r x = , s y 2 p 2 c 6(2 p 2 cu + dp 2 )

we have r y − sx = 2 p 2 (3ad − bcp 2 ) = 2 p 2 . This proves (5). For T2 , if the following conditions hold, then (3) and (6) are obtained; • a and d are odd, b and c are even and 3  b, and • a is even, b, c and d are odd and 3  b, respectively. < In a similar way, the case rs − → xy can be shown. For the opposite direction, we do calculations only for (2) and the plus sign. The others similar. Assume that 2 · 3 p 2 s, x ≡ 2ur (mod p), y ≡ 2us (mod p) and r y − sx = 2 p 2 . So there exist k, ∈ Z such that x = 2ur + kp 2 and y = 2us + p 2 . As r y − sx = 2 p 2 , we have r − ks = 2, or r2 − ks 2 = 1. Since  (r, s) = 1 and 2|s, r must be odd and must be even. Therefore the element r k/2 T = with determinant 1, is obtained. Since 2 · 3 p 2 s, T in N0 (22 3 p 2 ). s /2   It is easily seen that T (∞) = rs and T pu2 = xy . That is, rs → xy is an edge in  

F ∞, pu2 .

123

Graphs and Combinatorics (2017) 33:1531–1542

 Theorem 3.2 No edges of F ∞,

u p2



1539

cross in U . <

Proof Suppose that the edges ∞ → pu2 and y x1p2 − → y x2p2 cross in U , where all letters 1 2 x1 x2 u are positive integers. So y p2 < p2 < y p2 . By the edge conditions in Theorem 3.1, 1

2

we get x1 y2 − x2 y1 = −1 or x1 y2 − x2 y1 = −2. Therefore −1 y1

x1 y2 −x2 y1 y1 y2


x2 y2

< 0.

< uy2 − x2 < 0. Since uy2 − x2 ∈ Z Then for x1 y2 − x2 y1 = −1, we obtain that

and y1 = 1, 3, 4 or 12, this contradicts to the fact that there is no integer in (−1,0). Definition 3.3 By a directed circuit, we mean that a sequence v1 , v2 , · · · , vm of different vertices such that v1 → v2 → · · · → vm → v1 , where m ≥ 3. If m = 3, m = 4 and m = 6, then the circuit, directed or not, is called a triangle, a quadrilateral, and a hexagon, respectively. If m = 2, then we will call the configuration v1 −→ v2 −→ v1 a self paired. A graph which contains no circuit is called a forest.   Theorem 3.4 F ∞, pu2 has self paired edge if and only if 12u 2 ≡ −1 (mod p 2 ). Proof By transitivity, we can take the self paired edge Theorem 3.1, the proof follows.

1 0

→

u p2

→ 01 . According to



>

1 2 1 − → 25·49 → 12·49 is a self paired edge Example 1 If u = 2 and p = 7, then 12·49   2 in F ∞, 49 . By Theorem 3.1, it is easily seen that for first edge, 22 3 p 2 12 · 49, r y − sx = 49, 2 ≡ 1 · 2 (mod 49), and for second edge, p 2 25 · 49, r y − sx = −49, > 7 137 7 1 ≡ −12 · 2 · 2 (mod 49). Also, the self paired edge 12·169 − → 235·169 → 12·169 in   92 F ∞, 169 is obtained.   Theorem 3.5 F ∞, pu2 contains no triangle.

 Proof Suppose that F ∞, be taken

1 0

→

u p2

→

x y

→

u p2 1 0.



contains a triangle. From transitivity, the triangle can

By Theorem 3.1, y = p 2 or y = 2 p 2 .

If y = 2 p 2 , then we have 2u − x = ±1 and 2u ∓ 1 ≡ ±12u 2 (mod p 2 ) ⇒ 12u 2 ± 2u + 1 ≡ 0 (mod p 2 ) for the edge pu2 → xy . Moreover, since 1 ≡ −6ux (mod p 2 ) for the last edge, 12u 2 ± 6u + 1 ≡ 0 (mod p 2 ). Thus, 4u ≡ 0 (mod p 2 ). As p is prime number greater than 3, we get u ≡ 0 (mod p 2 ) which contradicts to (u, p 2 ) = 1. For the case y = p 2, a similar contradiction is obtained. Consequently, there is no

triangle in F ∞, pu2 .  Theorem 3.6 F ∞,

u p2



has no quadrilateral.

ˆ 2 3 p 2 ) is transitive, Proof Assume that it has a quadrilateral. Since the action on Q(2 1 u < k < m 1 it must be of the form 0 → p2 − → p2 − → np2 → 0 . From the last edge, n = 1 or n = 2.

123

1540

Graphs and Combinatorics (2017) 33:1531–1542

Let us prove only for the case n = 1. The proof for n = 2 is similar. For the edge < k m − → np 2 , we get k − m = −1 or k − m = −2 by the edge conditions. If p 2 = 2 or = 6 , then from Theorem 3.1 and third edge, we obtain k − 2m = −2 or k − 6m = −2. Therefore k must be even. Since (k, ) = 1 and is even, this is impossible. If = 4, then from second and third edges by Theorem 3.1, we have 4u − k = −1 and k − 4m = −1, that is 2u − 2m = −1. Therefore we obtain a contradiction 2|1. By similar calculations, for = 3 and = 12, we get the contradictions 3|2 and 6|1 respectively.

  Theorem 3.7 The subgraph F ∞, pu2 contains a hexagon iff 12u 2 ± 6u + 1 ≡ 0 (mod p 2 ).  Proof We firstly suppose that there is a hexagon in F ∞, action, we can take this hexagon of the form

u p2

 . Because of transitive

u < x1 < x2 < x3 < x4 1 1 → 2 − → − → − → − → → , 2 2 2 2 0 p y1 p y2 p y3 p y4 p 0 where all letters are positive integers. From the second edge and Theorem 3.1(vi), we get x1 = uy1 + 1 and x1 ≡ −12u 2 (mod p 2 ). Hence 12u 2 + uy1 + 1 ≡ 0

(mod p 2 ).

(3.1)

Also, for the last edge y1 (mod p 2 ), (3.2) 12 y1 (mod p 2 ). (3.3) x4 ≡ 2u + 6   12u 2 +uy1 +1 p2 ∈ N0 (22 3 p 2 ). So it is clear that Now we take the element T = −12u x4 ≡ u +

−12 p 2 12u+y1 1 2 = = T ( 0 ). In the next step, we show that y x2p2 2 must first show y x2p2 ≤ T 3 ( 01 ). 2 u(y 2 −12)+y Assume the contrary; y x2p2 > T 3 ( 01 ) = p21(y 2 −12) 1 . Hence 2 1 uy1 +1 y1 p 2

x1 y1 p 2

uy2 (y12 − 12) + y1 y2 < x2 (y12 − 12). Since

u p2

<

x2 , y2 p 2

(3.4)

then uy2 < x2 . So we get the equations − x2 < −uy2 , uy2 y12 < x2 y12 .

123

= T 3 ( 01 ). For this, we

(3.5) (3.6)

Graphs and Combinatorics (2017) 33:1531–1542

1541

From the Eqs. (3.4) and (3.5), uy2 y12 + y1 y2 < x2 y12 .

(3.7)

Therefore using the Eqs. (3.6) and (3.7), we obtain y1 y2 < 0. Since y1 , y2 > 0, this gives a contradiction. Hence one of the vertices of hexagon must be T 3 ( 01 ). Otherwise, we obtain a contradiction with Theorem 3.2. Consequently, y x2p2 = T 3 ( 01 ). 2 Let us now show that   uy1 (y12 − 24) + y12 − 12 x3 4 1 = T . = y3 p 2 0 y1 (y12 − 24) p 2 As above, we assume that

x3 y3 p 2

> T4

1 0 . So we have

uy1 y3 (y12 − 24) + y12 y3 − 12y3 < x3 y1 (y12 − 24). As

u p2

<

x3 , y3 p 2

(3.8)

then uy3 < x3 . Thus − x3 < −uy3 , uy3 y13 < x3 y13 .

(3.9) (3.10)

From the Eqs. (3.8) and (3.9), we get uy3 y13 + y12 y3 < x3 y13 .

(3.11)

Hence by the Eqs. (3.10) and (3.11), we obtain y12 y3 − 12y3 < 0. Since y3 > 0, we conclude that y12 − 12 < 0. Therefore y = 1, 2 or 3. Also, from Eqs. (3.2) and (3.3), 6|y1 or 12|y1 . So we have a contradiction. Consequently y x3p2 = T 4 ( 01 ). 3 Finally, for the last edge by Theorem 3.1, it must be y4 = 1 or y4 = 2. If y4 = 1, then < y1 = 12 by Eq.(3.2). Therefore for the edge 12u+1 − → xp42 , we get 12u+1−12x4 = −1, 12 p 2 that is 6(u − x4 ) = −1. We get the contradiction 6|1. < − → If y4 = 2, then y1 = 6 or y1 = 12 by Eq. (3.3). Let y1 = 12. For the edge 12u+1 12 p 2 x4 , we have 4(2u − x4 ) = −1 which again a contradiction. 2 p2 Thus, it must be y1 = 6 and y4 = 2. Therefore, from Eq. (3.1), we obtain 12u 2 + 6u + 1 ≡ 0 (mod p 2 ). If the circuit is decreasing, then 12u 2 − 6u + 1 ≡ 0 (mod p 2 ) (Fig. 1). Conversely, assume that 12u 2 ± 6u + 1 ≡ 0 (mod p 2 ). Using Theorem 3.1, it follows that u 6u ± 1 4u ± 1 3u ± 1 2u ± 1 1 1 → 2 → → → → → , 0 p 6 p2 4 p2 3 p2 2 p2 0  is a hexagon in F ∞,

u p2

 .



123

1542

11 49

Graphs and Combinatorics (2017) 33:1531–1542

67 6 49

45 4 49

34 3 49

23 2 49

7 2 169

11 3 169

15 4 169

23 6 169

4 169

   4  Fig. 1 The hexagons in subgraphs F ∞, 11 49 and F ∞, 169

Example 2 The following hexagons are obtained easily by Theorem 3.1 and Theorem 3.7   1 11 67 45 34 23 1 11 → → → → → → in F ∞, 0 49 6 · 49 4 · 49 3 · 49 2 · 49 0 49   1 4 23 15 11 7 1 4 → → → → → → in F ∞, 0 169 6 · 169 4 · 169 3 · 169 2 · 169 0 169 These are given in Fig. 1, respectively.   1 49 293 195 146 97 1 49 → → → → → → in F ∞, . 0 361 6 · 361 4 · 361 3 · 361 2 · 361 0 361

References 1. Akba¸s, M., Singerman, D.: The normalizer of Γ0 (N ) in PSL(2,R). Glasgow Math. 32, 317–327 (1990) 2. Akba¸s, M., Singerman, D.: The signature of the normalizer of Γ0 (N ). London Math. Soc. Lect. Note Ser. 165, 77–86 (1992) 3. Akba¸s, M., Ba¸skan, T.: Suborbital graphs for the normalizer of Γ0 (N ). Turk. J. Math. 20, 379–387 (1996) 4. Bigg, N.L., White, A.T.: Permutation Groups and Combinatorial Structures, London Mathematical Society Lecture Note Series, 33rd edn. CUP, Cambridge (1979) 5. Conway, J.H., Norton, S.P.: Monstrous moonshine. Bull. Lond. Math. Soc. 11, 308–339 (1979) 6. Güler, B.Ö., Be¸senk, M., De˘ger, A.H., Kader, S.: Elliptic elements and circuits in suborbital graphs. Hacet. J. Math. Stat. 40(2), 203–210 (2011) 7. Güler, B.Ö., Kör, T., Sanlı, ¸ Z.: Solutions to some congruence equations via suborbital graphs. SpringerPlus 5, 1327 (2016) 8. Kader, S., Güler, B.Ö., De˘ger, A.H.: Suborbital graphs for a special subgroup of the normalizer of Γ0 (m). Iran. J. Sci. Technol. A 34, 305–312 (2010) 9. Keskin, R.: Suborbital graphs for the normalizer of Γ0 (m). Eur. J. Comb. 27(2), 193–206 (2006) 10. Keskin, R., Demirtürk, B.: On suborbital graphs for the normalizer of Γ0 (N ). Electron. J. Comb. 16, 116 (2009). (18) 11. Lehner, J., Newman, M.: Weierstrass points of Γ0 (N ). Ann. Math. 79(2), 360–368 (1964) 12. Sims, C.C.: Graphs and finite permutation groups. Math. Z 95, 76–86 (1967)

123