ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 10 (2016) 349-357
Petrie polygons, Fibonacci sequences and
Farey maps
David Singerman , James Strudwick *
Received 5 June 2015, accepted 21 September 2015, published online 5 February 2016

Abstract
We consider the regular triangular maps corresponding to the principal congruence subgroups r(n) of the classical modular group. We relate the sizes of the Petrie polygons on these maps to the periods of reduced Fibonacci sequences.
Keywords: Regular map, Petrie polygon, Fibonacci sequence. Math. Subj. Class.: 05C10, 11B39, 20H05
1 Introduction
An interesting number theoretic problem is to determine the period of the Fibonacci sequence mod n. Here we look at the period a(n) of the Fibonacci sequence mod n up to sign. A Petrie polygon on a regular map is a zig-zag path through the map and an important invariant of a regular map is the length of a Petrie polygon. The maps we consider here are those that arise out of principal congruence subgroups r(n) of the classical modular group r. In this case It is shown that these lengths are equal to a(n). A particularly nice example is when n = 7. Here the regular map is the famous map on the Klein quartic and we find a(7) = 8 giving the title "The Eightfold Way" to the sculpture by Helaman Ferguson that represents Klein's Riemann surface of genus 3 derived from the Klein quartic. This is described in the book "The eightfold way: the beauty of Klein's quartic curve", a collection of papers related to the Klein quartic edited by Silvio Levy [5].
Let X be a compact orientable surface. By a map (or clean dessin d'enfant) on X we mean an embedding of a graph G into X such that X \ G is a union of simply-connected polygonal regions, called faces. A map thus has vertices, edges and faces. A directed edge is called a dart and a map is called regular if its automorphism group acts transitively on its darts. The platonic solids are the most well-known examples of regular maps. These are the regular maps on the Riemann sphere. We recall how we study maps using triangle groups. The universal map of type (m, n)is the tessellation of one of the three simply connected
* Department of Mathematical studies, University of Southampton, Southampton SO17 1EH, United Kingdom
E-mail addresses: ds@maths.soton.ac.uk (David Singerman), jes3g10@soton.ac.uk (James Strudwick)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
349
Ars Math. Contemp. 10 (2016) 255-268
Riemann surfaces, that is the Riemann sphere E, the Euclidean plane C, or the hyperbolic plane, H (depending on whether the genus of X is 0,1, or > 1) by regular m-gons with n meeting at each vertex. This map is denoted by M(m, n). The automorphism group, and also the conformal automorphism group, of M(m, n) is the triangle group r[2, m, n]. In general, a map is of type (m, n) if m is the least common multiple of the face sizes and n is the least common multiple of the vertex valencies. As shown in [3] every map of type (m, n) is a quotient of M(m, n) by a subgroup M of the triangle group r[2, m, n]. Then M is called a map subgroup of M(m, n) or sometimes a fundamental group of M(m, n), inside r[2, m, n]. A platonic surface is one that underlies a regular map. The map is regular if and only if M is a normal subgroup of r[2, m, n]. Thus a platonic surface is one of the form U/M where M is a normal subgroup of a triangle group and U is a simply connected Riemann surface.
It is permissible to let m or n, or both to be to. In this paper we are particularly interested in the case where m = 3, n = to. This means that the corresponding maps are triangular though in general we are not concerned with the vertex valencies. However, if the map is regular then we must have all vertex valencies equal. For example, the icosahedron is a triangular map with all vertices of valency 5.
To study triangular maps we use the triangle group [2,3, to] which is known to be the modular group r =PSL(2, Z) one of the most significant groups in mathematics. The regular maps correspond to normal subgroups of r. The most well-known normal subgroups of r are the principal congruence subgroups r(n) defined in section 5. We let M3(n) = M3(3, TO)/r(n). We call these maps principal congruence maps or PC maps.
For low values of n these maps are well-known. For n = 2,3,4, 5 we get the triangle, tetrahedron, octahedron and icosahedron respectively. These are the only PC maps of genus 0. For n = 6 we get the regular map {3,6}2.2 on the torus and for n = 7 we get the Klein map on Klein's Riemann surface of genus 3. (See [2, 1]).
2 Petrie polygons
A Petrie polygon in a map M is defined as a zig-zag path in the map. More precisely, we start at a vertex, then go along an edge to an adjacent vertex, the turn left and go to the next vertex and then turn right, etc., (or interchange left and right.) We have a path in which two consecutive edges belong to the same face but no three consecutive edges belong to the same face, [1, p. 54]. Eventually, in a finite regular map, we will come back to the original vertex.This path is called a Petrie path or Petrie polygon. The number of edges of this Petrie polygon is called the Petrie length of the map.
We now relate the Petrie polygons to triangle groups. From the triangle group r[2, m, n], we can form the extended triangle group r(2, m, n) which is the group generated by the reflections Ri, R2, R3 in the edges of a triangle with angles n/2, n/m, n/n where we choose our ordering so that r(2, m, n) has a presentation
(Ri,R2,R3|R2 = R2 = R3 = (R1R2)2 = (R2 R3)m = (R3Ri)n = 1). If we let X = R1R2, Y = R2 R3, Z = R3 R1, then we find that r[2, m, n] has a presentation (X, Y, Z |X2 = Ym = Zn = XYZ = 1).
In section 5.2 of [1, p. 54], it is shown that R1R2R3 is a transformation that goes one step around a Petrie polygon. Now
D. Singerman and J. Strudwick: Petrie Polygons, Fibonaci sequences and Farey maps
351
(Ri R2 R3 )2 — Ri R2 R3 Ri R2 R3 — Ri R2 R3 R2 R2 Ri R2 R3 — XY 1X 1Y
showing that Petrie length is twice the order of this commutator which implies that the Petrie length is independent of the Petrie polygon chosen; it is just a property of the map.
3 The Farey map
This is basically the map M(3, ro), which we abbreviate to M3. We construct it as follows. The vertices are the extended rationals Q U {ro} and two rationals | and d are joined by an edge if and only if ad — bc — ±1.
This map has the following properties.
(a)	There is a triangle with vertices 0, i, 0 called the principal triangle.
(b)	The modular group r acts as a group of automorphisms of M3.
(c)	The general triangle has vertices |, a+d, d.
Thus the Farey map (Figure 1) is a triangular map with triangular faces given by (c). In [7] it is shown that this is the universal triangular map in the sense that any other triangular map on an orientable surface is a quotient of M3 by a subgroup A of the modular group r. As M3 has vertices the extended rationals this means that every triangular map the vertices can be given coordinates which are A orbits of points in Q U {ro}. We shall denote the orbit of I by [| ]. This is illustrated in [2] where there are many examples, in particular coordinates for the triangular platonic solids are given. Also see Figure 2.
Figure 1: Farey map
4 The Petrie polygons of the Farey map
We consider a Petrie path in M3. By transitivity we may assume it's first edge goes from Wi — 0 to W2 — i .A left turn then takes us to W3 — i Now a right turn takes us to
W4 — i. By applying a modular transformation ^ d j to the vertices ro, 0 and 1 to the
352
Ars Math. Contemp. 10 (2016) 255-268
principal triangle we find that three consecutive vertices of the Petrie polygon are a, d, a+d, that is the third vertex is the Farey median of the previous two. As the first two vertices of the Petrie polygon are 1 and\ the kth vertex of the Petrie polygon is equal to f1 where fk is the kth element of the Fibonacci sequence defined by f0 = 0, f = 1, fk+1 = fk + fk-1. for k > 1. Thus the Petrie polygon is
10 112 3
0,1,1, 2, 3, 5 •••
Lemma 4.1. The matrix P = ^^ maps each vertex of the Petrie polygon of M3 to
the next one and also Pk = \fk—1 fk
\ Jk Jk+1
The proof follows immediately from the definition of the Fibonacci sequence, and induction.
Note that P having determinant -1 is not an element of r but T = P2 = ^ ^ is an element of r.
In the following sections we will consider the Petrie polygon modulo n. As | = —a, we introduce the following concept.
Definition 4.2. We call the least positive integer m with the property that fm-1 = ±1, mod n, fm = 0 mod n the semi-period <r(n) of the Fibonacci sequence mod n. The period n(n) is the least positive integer m such that fm-1 = 1 mod n, fm = 0 mod n.
For example if m = 7, the Fibonacci sequence mod 7 is 0,1,1,2,3,5,1,6,0, so that <r(7) = 8 and n(7) = 16. The function n has been quite well-studied in the literature and is often called the Pisano period. See [8].
5 The principal congruence subgroups
The most well-known normal subgroup of the modular group are the principal congruence subgroups. Let n G Z, Then the principal congruence subgroup of level n in r is the subgroup
r<»>={(: d) g r:(; d)=± (;;) mod „}
Now r(n) is a normal subgroup of r and so corresponds to a regular map M3 (n) which lies on the surface H*/r(n) where H* = H U Q U {to}. Another important group for us is r1(n). This is defined as
r1<»>={(: d) G r:(: d)=± (0 b) m-^«}
where 0 < b < n.
We will not make use of this subgroup but in [2] it was shown that the left cosets of r1 (n) in r are in one-to-one correspondence with the vertices of M3(n). r(n) is a normal subgroup of r of index
n3 1
ynP|n(1 - ).	(1)
D. Singerman and J. Strudwick: Petrie Polygons, Fibonaci sequences and Farey maps
353
6	The Petrie polygons of M3(n)
Our principle object of study are the Petrie polygons of the PC-maps M3(n). We can regard M3(n) as M3(3, TO)/r(n), that is as a quotient of the Farey map. We illustrate our study with the classical regular map M3(7). This is known as the Klein map and is a map of type {3, 7}. This lies on Klein's Riemann surface of genus 3, known as the Klein quartic. Petrie polygons for this map appear on page 320 in the classic paper [4], although they were not called Petrie polygons there. In fact, Petrie polygons are named after John Flinders Petrie (1907-1972), and Klein's paper [4] was written in 1878. Three of the Petrie polygons are drawn on page 320 of "The Eightfold Way" [5]. The eight in the title comes from the fact that the size of the Petrie polygons is 8. This will be a special case of results in this paper where we determine the sizes of of the Petrie polygons in PC maps.
In general we observe that the group r/r(n) has a transitive action on the Petrie polygons of M3(n). For r clearly has a transitive action on the darts of M3(to), and so r/r(n) has an induced action on the darts of M3(n). Clearly, this action will give a transitive action on the set of Petrie polygons of M3(n).
The vertices of M3(n) are equivalence classes of vertices of M3(3, to). We let [a] denote the equivalence class of | in M3(n) and [|] is joined by an edge to [d] in M3(n) if and only if ad — bc = 1 mod n.
The points [ 1 ], [ 0 ], • • • [ /-1 ] • • • form the vertices of a Petrie polygon which we call Pe(n).	"
Recall the definition of the semiperiod <r(n) in section 4.
Theorem 6.1. The Petrie length ofPe(n) is equal to <r(n).
Proof. /CT(„)-1 = fa(n)+1 = ±1, fa(n) = 0, so the result follows.	□
Note that Pe(n) is a Petrie polygon on M3(n).
The Fibonacci sequence mod 7 is 0,1,1,2,3,5,1,6,0 and the Petrie polygon Pe(7) has vertices [0], [0], [ 1 ], [ 1 ][2], [|], [f ], [ 1 ]. The next vertex is [] which is equal to [ 1 ] so we have closed up our polygon, which has 8 vertices. This polygon is illustrated in Figure 2, where we denote [a] by (a, b). This picture of the Klein surface comes from [2]. The same picture also appears in at the paper [6]. We can apply the same idea for other values of n. For example M5 is the icosahedron and <r(5) = 10 which is the known Petrie length for the icosahedron.
7	The universal Petrie polygon
To determine the stabiliser of a Petrie polygon it is useful to introduce a new idea. We first extend the standard Fibonacci sequence to include negative numbers. We still want the basic recurrence relation /t-1 + /t = /t+1 to hold, so this extended Fibonacci sequence is
----3, 2, —1,1,0,1,1, 2, 3, •••
so that /-k = ( — 1)fc-1/k. The universal Petrie polygon Pe(ro) is the infinite polygon with vertices -f^- where k G Z and edges the closed intervals [ f1, -f- ]. Note that
/j- = (-1)— = — and hence the transformation R : t ^ — 1 represented by the matrix f ^ ^ j is an automorphism of Pe(ro). Also T = P2 = i1 ^ j is an
354
Ars Math. Contemp. 10 (2016) 255-268
Figure 2: Petrie Polygon
automorphism of Pe(TO) that belongs to r. Note that R2 = (TR)2 = I so that T and R generate an infinite dihedral group of automorphisms of Pe(TO).
Theorem 7.1. The automorphism group of Pe( to) in r is equal to (T, R) = D^.
Proof. The group (T, R) is a group of automorphisms of Pe(TO). We show that it acts transitively on Pe(TO). First of all, P maps each Farey fraction two steps along the Farey sequence as
T () fk
fk-1 + fk = fk+1 = fk+l fk-1 + 2fk fk+1 + fk fk+2
Thus the union of the orbits of 1 and 0 under (T) is the whole of Pe(TO), and as R( 1) = 0, (T, R) acts transitively on Pe(TO). We note that the stabiliser of 1 = to in Aut Pe(TO) is trivial. For the stabilizer of to in r consists of the transformations z ^ z + m, where m € Z, and the only translation that preserves Pe(TO) is the identity, Now suppose that
A € AutPe(TO). Then A(to) = f-1. By transitivity, there exists B € (T, R)such that B (to) = f1 .Thus A-1B fixes to and thus A = B.	□
We now search for the automorphism group of Pe(n). Theorem 7.2. The automorphism group ofPe(n) is isomorphic to Da(n)/2.
D. Singerman and J. Strudwick: Petrie Polygons, Fibonaci sequences and Farey maps
355
Proof. We have an epimorphism 6 : r —> PSL(2, Zn) and 6(T) = P = ^ ^J, where we think of this matrix as lying in PSL(2, Zn). Now Po(n) = (fa}n)-1 fo(n)
V Jo(n) Jo(n)+1/
Now fa(n) = 0 mod n and fo(n)-1 = fo(n)+1 = ±1, by the definition of a(n). Thus Po(n) = ±1 and so To(n)/2 = ±1. which is the identity in PSL (2,Zn) Thus the automorphism group of Pe(n) is generated by R and T with R2 = (RT)2 = To(n)/2 = 1 and hence (R, T} = Do(n)/2 of order a(n).	□
It is interesting to see how this theorem works in practice, so let us go back to our example of n = 7 as illustrated in Figure 2. As a(7) = 8 we have an action of D4 on Pe(7) an 8-sided polygon . The element T has two cycles of length 4, namely
(1,0) (1,1) (2, 3) (5,1) (1,0) (0,1) (1, 2) (3, 5) (1, 6) (0,1)
and for the involution R we have (1,0) ^ (0,1), (1,1) ^ (6,1), (1,2) ^ (5,1), (2, 3)
^ (4,2).
(Note that [§] = [ ] = [f] so that (3, 5) = (4,2), etc.)
As r/r(n) acts transitively on the darts of M3(n) we use equation (1) in section 5 to obtain
Corollary 7.3. The number of Petrie polygons on M3 (n) is equal to
n3 1 np|n(1 - P2 ).
2a(n)
Example. Let n = 7. Then a(7) = 8. The number of Petrie polygons of M3(7) is equal to 21. Klein drew three of them in [5]. The others can be found by rotating these through 2nk/7, for k = 1, ••• 6.
8 More about &(n)
Theorem 8.1. For all positive integers m > 2, a(m) is even.
Proof. Po(m) = (fo(m)-1 fo(m) \ = ±1 mod m V Jo(m) Jo{m) + 1 J
Thus (detP)o(m) = 1 mod m, so (- 1)o(m) = 1 mod m and thus a(m) is even. □
Exactly the same proof shows that n(m) is even for m > 2. A much easier proof than that given in [8].
Let p = 1+2T5 (the golden ratio) and p* = . Note that pp* = -1 and p + p* = 1.
Let Zn[p] = {a + bp|a, b G Z/(n)} and if a = a + bp, define a* = a + bp*. Then
(aft )* = a* ft *.
We define the norm N on Zn[p] by N(a) = aa*. Then N(aft) = N(a)N(ft). We call a a unit if N(a) = ±1, so that p is a unit. The units of Zn [p] form a group Z*n[p] under multiplication.
Theorem 8.2. a(n) is the order of p in Z*n [p], if fo(n)-1 = 1 and is equal to half the order of p if fo(n)-1 = -1. Inallcases n(n) is equal to the order of p in Z *n[p].
356
Ars Math. Contemp. 10 (2016) 255-268
Proof. From p2 = p +1 we can use induction to prove that pm = fmp + fm_1 Thus if m = <r(n), fm =0 and fm_1 = ±1. Thus pCT(n) = 1 if fCT(„)_1 = 1 and is equal to -1 if fa(n)_1 = -1 and in the latter case the order of p is 2n.	□
The proof for n is similar. 9 The Pisano period and the semiperiod
There is a lot about the Pisano period n(m) in the literature . For example, see [8], where the Pisano period is calculated for all primes less than 2000. Very little is known about the semiperiod <r(m). We end with a few results comparing the two.
Lemma 9.1. n(m) = a(m) if and only if fa(m)_1 = 1. n(m) = 2<r(m) if and only if
fa(m)_ 1 = -1
Proof. Let k be the least integer such that, modulo m, fk_1 = -1, fk = 0. Then k = <r(m)
and fa(m)+r = -fa(r), so that f2a(m)_1 = -fa(m)_ 1 = 1,f2a(m) = 0 and n(m) =
2a(m).
Alternatively, fk_1 = +1 and then n(m) = a(m).	□
We want to determine which of these occur. We give some partial answers. From Theorem 9.2 we see that a(m) = n(m) if and only if pm_1 = 1 and a(m) = 2n(m) if and only if pm_1 = +1.
Theorem 9.2. Let p = ±2 mod 5 be an odd prime. Then n(p) = 2a(p).
Proof. The point is that 5 is a quadratic residue mod p if and only if p = ±1 mod 5. Otherwise 5 is a non-residue and by adjoining a/5 to Fp, the finite field of p elements which we can take to be Z/pZ, we get a finite fieldK of characteristic p with p2 elements. This field can be considered to be Fp/I, Where I is the ideal generated by x2 - x - 1, which we can identify with all elements of the form a + bp, where a, b e Fp the field with p elements. The polynomial x2 - x - 1 has no roots in Fp but two roots in K interchanged by the Frobenius automorphism ^ : a —> ap. If a is a root of this polynomial then the other root is ap = 1 - a and hence so that ap+1 = a - a2 = -1. Thus, by Theorem 8.2 and Lemma 9.1, n(p) = 2a(p).	□
Theorem 9.3. Let p = 11,19 mod20. Then n(p) = a(p).
Proof. We have p = ±1 mod 5 and so 5 has a square root in Fp the finite field with p elements and hence p e Fp. Its multiplicative group has order p - 1. Now
pn(p) = fn(p)p + fn(p)_ 1 = 1mod p
Therefore n(p) is a divisor of p - 1. Now p = 3 mod 4 so that p = 4k + 3 for some integer k. This p - 1 = 4k + 2. If n(p) = 2a(p), then a(p) is a divisor of 2k + 1 and thus a(p) is odd contradicting Theorem 8.1. Therefore a(p) = n(p).	□
We would like to thank Tom Harris for helping us with the results in section 9 and the referee for his careful reading of the manuscript.
D. Singerman and J. Strudwick: Petrie Polygons, Fibonaci sequences and Farey maps
357
References
[1]	H. S. M. Coxeter and W. O. J. Moser, Generators and relations for discrete groups, volume 14 of Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas], Springer-Verlag, Berlin-New York, 4th edition, 1980.
[2]	I. Ivrissimtzis and D. Singerman, Regular maps and principal congruence subgroups of Hecke groups, European J. Combin. 26 (2005), 437-456, doi:10.1016/j.ejc.2004.01.010.
[3]	G. A. Jones and D. Singerman, Theory of maps on orientable surfaces, Proc. London Math. Soc. (3) 37 (1978), 273-307.
[4]	F. Klein, Ueber die Transformation siebenter Ordnung der elliptischen Functionen, Math. Ann. 14 (1878), 428-471, doi:10.1007/BF01677143.
[5]	S. Levy, The eightfold way: the beauty of Klein's quartic curve, volume 35, Cambridge University Press, 1999.
[6]	E. Schulte and J. M. Wills, A polyhedral realization of Felix Klein's map {3, 7}8 on a Riemann surface of genus 3, J. London Math. Soc. (2) 32 (1985), 539-547, doi:10.1112/jlms/s2-32.3.539.
[7]	D. Singerman, Universal tessellations, Rev. Mat. Univ. Complut. Madrid 1 (1988), 111-123.
[8]	D. D. Wall, Fibonacci series modulo m, Amer. Math. Monthly 67 (1960), 525-532.