Vietnam Journal of Mathematics 33:2 ( 2005) 189–197
Fibonacci Length of Direct Products of Groups
H. Doostie
1
and M. Maghasedi
2
1
Mathematics Department, Teacher Training University,
49 Mofateh Ave., Tehran 15614, Iran
2
Mathematics Section Doctoral Research Department,
Islamic Azad University, P.O. Box. 14515-775, Tehran, Iran
Received July 7, 2004
Revised December 4, 2004
Abstract. For a non-abelian finite group G = a
1
,a
2
, ,a
n
 the Fibonacci length
of
G with respect to the ordered generating set A = {a
1
,a
2
, ,a
n
} is the least
integer
l such that for the sequence of elements x

i
= a
i
, 1 ≤ i ≤ n, x
n+i
=

n
j=1
x
i+j−1
,i≥ 1,ofG, the equations x
l+i
= a
i
, 1 ≤ i ≤ n hold. The question
posed in
2003 by P. P. Campbell t hat ”Is there any relationship between the lengths
of finite groups
G, H and G × H ?” In this paper we answer this question when at
least one of the groups is a n on-abelian 2 -generated group.
1. Introduction
Let G = A be a finite non-abelian group where, A = {a
1
,a
2
, ,a
n
} is an
ordered generating set. The sequence

x
i
= a
i
, 1 ≤ i ≤ n, x
n+i
=
n

j=1
x
i+j−1
,i≥ 1
of the elements of G, denoted by F
A
(G), is called the Fibonacci orbit of G with
respect to A, and the least integer l for which the equations x
l+i
= x
i
, 1 ≤
i ≤ n hold, is called the Fibonacci length of G with respect to A and will be
denoted by LEN
A
(G). The notions of basic Fibonacci orbit and basic Fibonacci
length are almost similar. Indeed, the basic Fibonacci orbit of length m is also
defined to be the same sequence of the elements of G such that m is the least
integer where the equations x
1
θ = x

m+1
, x
2
θ = x
m+2
, , x
n
θ = x
m+n
hold
190 H. Doostie and M. Maghasedi
for some θ ∈ Aut(G). The integer m is called the basic Fibonacci length of
G with respect to A and will be denoted by BLEN
A
(G). It is proved in [2]
that BLEN
A
(G) divides LEN
A
(G), for 2-generated finite groups. Obviously
A ∪{b
1
,b
2
, ,b
k
},k ≥ 1,b
1
= b
2

= ··· = b
k
= 1 is also a generating set for
G, however, the Fibonacci lengths with respect to A and with respect to this
generating set are different. We will use this new generating set to make possible
our calculations.
Since 1990 the Fibonacci length has been studied and calculated for certain
classes of finite groups ( one may see [1, 2, 4, 7], for examples), and certain
original questions have been posed by Campbell in [5]. We answer one of these
questions which is: how can one calculate the Fibonacci length of G×H (external
direct product of groups G and H) in terms of the Fibonacci lengths of G and
H?
For a finite number of the groups G
1
,G
2
, , G
k
we use the notation Dr
k
G
i
for the external direct product (or, simply the direct product) G
1
×G
2
×···×G
k
.
Our first attempt is to calculate LEN

{a,b,e}
(G × H)whereG = a, b is a
non-abelian finite group and H = e is a cyclic group of order m; then we will
calculate LEN
{a,b,c,d}
(G × H)whereG = a, b and H = c, d are non-abelian
finite groups.
For every positive integer m,wedefinethepositiveintegerk(m, 3) to be the
minimal length of the period of series (g
i
mod m)
+∞
−∞
,where
g
0
= g
1
=0,g
2
=1,g
i
= g
i−1
+ g
i−2
+ g
i−3
.
This number is similar to the Wall number k(m) of Wall [10], where the Wall

number is defined for the series (f
i
mod m)
+∞
−∞
such that
f
0
= f
1
=1,f
i
= f
i−1
+ f
i−2
.
Following Wall [10] one may also prove the existence of k(m, 3) for every positive
integer m. We will use 1 for 1
G
, the identity of the group G. Our main results
are the following propositions. Propositions A, B and C give explicit formulas
for computing the lengths of direct products of some groups, and Propositions
D and E are the generalization of [2] for LEN
{a,b}
(D
2n
)andLEN
{a,b}
(Q

2
n
)
(see [2]).
Proposition A. For every 2-generate d non-abelian finite group G = a, b and
every cyclic group H = e of order m,
LEN
{a,b,e}
(G × H)=l.c.m.(k(m, 3),LEN
{a,b,1}
(G)).
Proposition B. Fo r every 2-gener ated non-abelian finite groups G = a, b and
H = c, d,
LEN
{a,b,c,d}
(G × H)=l.c.m.(LEN
{a,b,1,1}
(G),LEN
{1,1,c,d}
(H)).
Fibonacci Length of Direct Products of Groups 191
Proposition C. For a positive integer n,letG
i
= a
i
,b
i
, 1 ≤ i ≤ n be
non-abelian 2-generated finite groups. For every i (1 ≤ i ≤ n) define A
i

=
{a
i,1
,a
i,2
, ,a
i,2n
},asfollows,
a
i,j
=
⎧
⎪
⎨
⎪
⎩
b
i
, if j =2i,
a
i
, if j =2i − 1,
1
G
i
, if j =2i, 2i − 1,
(j =1, 2, ,2n). Then,
LEN
{a
1

,b
1
,a
2
,b
2
, , a
n
,b
n
}
(Dr
n
G
i
)=l.c.m
1≤i≤n
LEN
A
i
(G
i
).
Consider the dihedral groups D
2n
= a, b|a
2
= b
n
=(ab)

2
=1 and the
generalized quaternion groups Q
2
n
= a, b|a
2
n−1
=1,b
2
= a
2
n−2
,b
−1
ab = a
−1
,
where n ≥ 3. The followings are two numerical results on these groups.
Proposition D.
(i) For every n ≥ 3 and k ≥ 1, LEN
{a
1
,a
2
, ,a
k
,a,b}
(D
2n

)=2k +6 where,
a
1
= a
2
= ···= a
k
=1.
(ii) For every n ≥ 3, LEN
{a,b,1}
(D
2n
)=
8n
g.c.d(4,n)
, LEN
{a,b,1,1}
(D
2n
)=
10n
g.c.d(4,n)
,
and in general, for an integer k ≥ 3 and for every i ( 1 ≤ i ≤ k) we define
A
i
= {a
1
,a
2

, ,a
k+1
,a
k+2
},where
a
m
=
⎧
⎪
⎨
⎪
⎩
a, if m = i,
b, if m = i +1,
1, otherwise.
Then, LEN
A
i
(D
2n
)=
(2k+6)n
g.c.d(n,4)
q
i,k,n
,where,q
i,k,n
is the least positive integer
such that for all values of r (3 ≤ r ≤ k − i +1),

r! | 2
r

2q
i,k,n
g.c.d(4,n)

2nq
i,k,n
g.c.d(4,n)
+1



2nq
i,k,n
g.c.d(4,n)
+ r − 1

.
Proposition E. For an integer k ≥ 3 and for every i (1 ≤ i ≤ k) let A
i
be as
in the Proposition D. Then, LEN
A
i
(Q
2
n
)=2k +6.

2. Proofs
ProofofPropositionA.Let H = e and G = a, b,soG = a, b, 1.Consider
the Fibonacci sequence of the elements of G = a, b, 1 and G × H = a, b, e as
x
1
= a, x
2
= b, x
3
=1,x
i
= x
i−3
x
i−2
x
i−1
,i≥ 4,
and
y
1
= a, y
2
= b, y
3
= e, y
i
= y
i−3
y

i−2
y
i−1
,i≥ 4,
respectively. For every n ≥ 1, y
n
= x
n
.e
g
n
,for,
y
1
= a = x
1
= x
1
.e
0
= x
1
.e
g
1
,
y
2
= b = x
2

= x
2
.e
0
= x
2
.e
g
2
,
y
3
= e =1.e = x
3
.e
1
= x
3
.e
g
3
.
192 H. Doostie and M. Maghasedi
Using an induction method, the hypothesis gives us
y
n+1
= y
n−2
y
n−1

y
n
= x
n−2
.e
g
n−2
.x
n−1
.e
g
n−1
.x
n
.e
g
n
and since e is a central element of G × H,then
y
n+1
= x
n−2
.x
n−1
.x
n
.e
g
n
+g

n−1
+g
n−2
= x
n+1
e
g
n+1
.
If l = LEN
{a,b,e}
(G × H)thenl is the least integer such that y
l+1
= a, y
l+2
= b
and y
l+3
= e. This leads to the equations x
l+1
.e
g
l+1
= a, x
l+2
.e
g
l+2
= b and
x

l+3
.e
g
l+3
= e. Equivalently, we get two classes of the equations as follows:
x
l+1
= a, x
l+2
= b, x
l+3
=1
and
g
l+1
≡ 0modm, g
l+2
≡ 0modm, g
l+3
≡ 1modm.
The first and second classes of the equations prove the divisablity of l by
LEN
{a,b,1}
(G)andk(m, 3), respectively. Since l is the least integer satisfying
these properties, so the result follows.

Proofs of Pr opositions B and C. Let G = a, b, H = c, d and G×H = a, b, c, d
where, [a, c]=[a, d]=[b, c]=[b, d]=1. ConsiderG and H as G = a, b, 1, 1
and, H = 1, 1,c,d. Then, the sequences of elements of these groups with
respect to these ordered generating sets are

x
1
= a, x
2
= b, x
3
= x
4
=1,x
i+1
= x
i−3
x
i−2
x
i−1
x
i
,i≥ 4,
y
1
= y
2
=1,y
3
= c, y
4
= d, y
i+1
= y

i−3
y
i−2
y
i−1
y
i
,i≥ 4,
z
1
= a, z
2
= b, z
3
= c, z
4
= d, z
i+1
= z
i−3
z
i−2
z
i−1
z
i
,i≥ 4,
respectively.
Wecanthenprovez
n

= x
n
y
n
by an induction method on n.Nowletl be
the least positive integer such that all of the equations
z
l+1
= a, z
l+2
= b, z
l+3
= c, z
l+4
= b.
hold (i.e. l = LEN
{a,b,c,d}
(G)), then by substituting for z
l+1
, z
l+2
, z
l+3
and
z
l+4
the result follows by a similar way to that of Theorem A. Theorem C may
be proved in a similar way.

ProofofPropositionD.

(i) For k ≥ 1 we consider the Fibonacci sequence of the elements. For instance
if D
2n
= 1, 1,a,b i.e., k =2thenwehavex
1
= x
2
=1,x
3
= a, x
4
= b, x
5
=
ab, x
6
=(ab)
2
=1,x
7
=(ab)
4
=1,x
8
= bab = a, x
9
= aba = b
−1
,x
10

=
ab
−1
,x
11
= x
12
=1,x
13
= a, x
14
= b.So,LEN
{1,1,a,b}
(D
2n
) = 10. In general
every element of the sequence x
1
= x
2
= ··· = x
k
=1
G
,x
k+1
= a, x
k+2
=
b, x

k+3
= x
1
x
2
x
k+2
, of the group D
2n
=<a
1
, ,a
k
,a,b > may be
represented as
Fibonacci Length of Direct Products of Groups 193
x
i
=
⎧
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪

⎪
⎩
a, if i ≡−2ork +1 mod 2k +6,
b, if i ≡ k +2 mod 2k +6,
b
−1
, if i ≡−1mod2k +6,
ab
−1
, if i ≡ 0mod2k +6,
1, otherwise.
where, i ≥ k + 3. This may be proved by induction on i. So, considering the
definition of the Fibonacci length gives the result at once.
(ii) Consider the Fibonacci sequence of D
2n
= a, b, 1 as
x
1
= a, x
2
= b, x
3
=1,x
i
= x
i−3
x
i−2
x
i−1

,i≥ 4.
For every k ≥ 4, every element of this sequence can be represented by
x
k
=
⎧
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎩
a, if k ≡ 1mod4,
b
(−1)
k−2
4
, if k ≡ 2mod4,
b
(−1)
k−3
4
.
k−3

2
, if k ≡ 3mod4,
ab
(−1)
k+4
4
.
k−2
2
, if k ≡ 0mod4.
If l = LEN
{a,b,1}
(D
2n
)thenx
l+1
= a, x
l+2
= b,andx
l+3
=1.Sol ≡ 0mod4,
and then b
(−1)
l
4
= b yields l ≡ 0mod8. Moreover,b
(−1)
l
4
.

l
2
=1holdsif
and only if
l
2
is divisible by n. Consequently, considering three cases for n as
n ≡ 0mod4,n ≡ 1mod4orn ≡ 2 mod 4, we get l =2n, l =8n or l =4n,
respectively. i.e., l =
8n
g.c.d.(n,4)
, as desired.
The Fibonacci sequence of the group G = a, b, 1, 1 is the sequence
x
1
= a, x
2
= b, x
3
= x
4
=1,x
i
= x
i−4
x
i−3
x
i−2
x

i−1
,i≥ 5.
It is easy to prove that for every k ≥ 5,
x
k
=
⎧
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩
ab
2(
k
5
)

2
−1
, if k ≡ 0mod5,
a, if k ≡ 1mod5,
b
(−1)
k−2
5
, if k ≡ 2mod5,
b
2(−1)
k−3
5
.
k−3
5
, if k ≡ 3mod5,
b
2(−1)
k−4
5
.
k−4
5
.
k+1
5
, if k ≡ 4mod5.
If l = LEN
{a,b,1,1}

(D
2n
) then in a similar way as for (ii) we deduce that l ≡ 0
mod 5, and almost a simple computation gives us l =
10n
g.c.d.(n,4)
.
In general case every element of the Fibonacci sequence of D
2n
with respect
to A
i
may be represented by
194 H. Doostie and M. Maghasedi
x
j
=
⎧
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪

⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩
a, if j ≡ i mod k +3,
b
(−1)
s
, if j ≡ i +1 mod k +3,
b

(−1)
s
2s
, if j ≡ i +2 mod k +3,
b
(−1)
s
2s(s+1)
, if j ≡ i +3 mod k +3,
b
(−1)
s
2
3
3!
s(s+1)(s+2)
, if j ≡ i +4 mod k +3,
.
.
.
b
(−1)
s
2
k+1−i
(k+1−i)!
s(s+1)(s+2) (s+k−i)
, if j ≡ k +2 mod k +3,
ab
(−1)

s
α
j
, if j ≡ 0modk +3,
1, otherwise,
where s =

j
k+3

and
α
l
=1+
k−i+1

r=1
2
r
r!
t(t +1) (t + r − 1)
that t =
j
k+3
− 1. ( [x] is used for the integer part of the real x.) This may be
proved by induction method on j.Letl = LEN
A
i
(D
2n

), by a similar method
as above we get l ≡ 0modk +3and l must satisfy all of the relations
(i) 2 |
l
k+3
,
(ii) n |
2l
k+3
,
(iii) n |
2
r
r!

l
k+3

l
k+3
+1



l
k+3
+ r − 1

, for all 3 ≤ r ≤ k − i +1.
The relations (i) and (ii) yield l =

(2k+6)n
g.c.d(4,n)
q
i,k,n
,where,q
i,k,n
is a positive
integer, and by (iii) we get
n |
2
r
r!

2nq
i,k,n
g.c.d(4,n)

2nq
i,k,n
g.c.d(4,n)
+1



2nq
i,k,n
g.c.d(4,n)
+ r − 1

,

for all r where, 3 ≤ r ≤ k − i + 1, and this holds if and only if
r! | 2
r

2q
i,k,n
g.c.d(4,n)

2nq
i,k,n
g.c.d(4,n)
+1



2nq
i,k,n
g.c.d(4,n)
+ r − 1

,
for all r where, 3 ≤ r ≤ k − i + 1. This completes the proof.

Note. Certain values of the sequence {q
i,k,n
} is given as follows, for instance,
q
i,k,n
=1ifi = k or i = k − 1, and n ≥ 3,
q

i,4,3
=
⎧
⎪
⎨
⎪
⎩
3, if i =1or 2,
1, if i =3,
4, if i =4,
q
i,4,4
=1,where,i =1, 2, 3, 4,
q
i,4,6
=

3, if i =1or 2,
1, if i =3or 4.
ProofofPropositionE.Let {x
j
}
∞
j=1
be the Fibonacci sequence of Q
2
n
with
respect to A
i

. We consider three cases
Fibonacci Length of Direct Products of Groups 195
Case I. i =1. Inthiscasewehavex
1
= a, x
2
= b, x
3
=1, , x
k+2
=1and
for every j where, k +3≤ j ≤ 2k +6, weget
x
j
=
⎧
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪

⎪
⎪
⎪
⎩
ba
−1
, if j = k +3,
b
2
a
−1
, if j = k +4,
b
3
a
−2
, if j = k +5,
b
2
, if j = k +6,
b
3
a
−1
, if j =2k +6,
1, otherwise.
Since then x
2k+7
= a, x
2k+8

= b, x
2k+9
= x
2k+10
= = x
3k+8
=1, so,
LEN
A
1
(Q
2
n
)=2k +6.
Case II. i = k+1. Then we get x
1
= x
2
= x
3
= = x
k
=1,x
k+1
= a, x
k+2
= b
and for every j where, k +3≤ j ≤ 2k +6,
x
j

=
⎧
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩
ba
−1
, if j = k +3,
b
2
, if j = k +4,
a
−1
, if j =2k +4,
b

3
a
−2
, if j =2k +5,
ba
−1
, if j =2k +6,
1, otherwise.
So, x
2k+7
= x
2k+8
= x
2k+9
= ···= x
3k+6
=1,x
3k+7
= a and x
3k+8
= b.Then
LEN
A
k+1
(Q
2
n
)=2k +6.
Case III. Let i =1andi = k +1. Thenx
1

= a
1
,x
2
= a
2
, , x
k
= a
k
,x
k+1
=
a
k+1
,x
k+2
= a
k+2
and for every j where, k +3≤ j ≤ 2k +6,
x
j
=
⎧
⎪
⎪
⎪
⎪
⎪
⎪

⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩
ba
−1
, if j = k +3,
b
2
if j = k +4,
a
−1
if j = k + i +3,
b
3
a
−2
if j = k + i +4,

b
2
if j = k + i +5,
b
3
a
−1
if j =2k +6,
1otherwise.
So x
2k+7
= a
1
,x
2k+8
= a
2
, , x
3k+8
= a
k+2
. Consequently LEN
A
i
(Q
2
n
)=
2k + 6. This completes the proof.


3. Conclusions
We give here certain numerical results on LEN and BLEN of the groups D
k
2n
(= Dr
k
D
2n
, the direct product of k copies of D
2n
)andQ
k
2
n
(= Dr
k
Q
2
n
), by
applying the propositions of Sec. 2.
Remark 1. LEN(Q
k
2
n
)=4k +2.
196 H. Doostie and M. Maghasedi
Proof. By the Propositions C and E.

Remark 2. LEN(D

2
2n
)=
10n
g.c.d(4,n)
and LEN (D
k
2n
)=
(4k+2)n
g.c.d(4,n)
q
1,2k−2,n
, k ≥ 3.
Proof. To the first part we use Proposition D and get LEN
{a,b,1,1}
(D
2n
)=
10n
g.c.d(4,n)
,andLEN
{1,1,a,b}
(D
2n
) = 10. Then Proposition B yields
LEN
{a,b,c,d}
(D
2n

× D
2n
)=l.c.m.(10,
10n
g.c.d(4,n)
)=
10n
g.c.d(4,n)
.
To prove the second part, consider the definition of q
i,k,n
and get
q
j,2k−2,n
| q
1,2k−2,n
, 2 ≤ j ≤ 2k − 2.
Then LEN
A
j
(D
2n
) | LEN
A
1
(D
2n
), for every j (2 ≤ j ≤ 2k −2) and Proposition
C yields the result LEN (D
k

2n
)=
(4k+2)n
g.c.d(4,n)
q
1,2k−2,n
as desired.

Remark 3. Let A
i
be defined as in Proposition D. Then, for every n ≥ 3
(i) 2 × BLEN
A
i
(D
2n
)=LEN
A
i
(D
2n
),
(ii) BLEN
A
i
(Q
2
n
)=LEN
A

i
(Q
2
n
).
Proof. Considering the Fibonacci sequences of elements and using the similar
method as in Propositions D and E we get the results immediately.

Acknowledgements. The authors are greatly indebted to the referee for his or her
suggestions that led to the improvement of this work.
References
1. H. Aydin and G. C. Smith, Finite p-quotients of some cyclically presented groups,
J. London Math. Soc. 49 (1994) 83 - 92.
2. C. M. Campbell, H. Doostie, and E. F. Robertson, Fibonacci length of generating
pairs in groups, In
Applications of Fibonac ci numbers,G.A.Bergumetal.
(Eds.), Vol. 5, 1990, pp. 27 - 35.
3. C. M. Campbell, P. P. Campbell, H. Doostie, and E. F. Robertson, On the Fi-
b onacci length of powers of dihedral groups, in
Applications of Fibonacci num-
bers
, F. T. Howard (Ed.), Vol. 9, 2004, pp. 69-85.
4. C. M. Campbell, P. P. Campbell, H. Doostie, and E. F. Robertson, Fibonacci
length for certain metacyclic groups, Algebra Colloquium 11 (2004) 215 - 222.
5. P. P. Campbell, Fibonacci Length and Efficiency in Group Presentations,Ph.D.
Thesis, U niversity of St. Andrews, Scotland, 2003.
6. H. Doostie and C. M. Campbell, Fibonacci length of automorphism groups in-
volving Tribonacci numbers, Vietnam J. Math. 28 (2000) 57 - 65.
7. H. Doostie and R. Golamie, Computing on the Fibonacci lengths of finite groups,
Internat. J. Appl. Math.

4 (2000) 149 - 156.
8. GAP, GAP-Groups, Algorithms, and Programming, Version 4.3, Aachen, St.
Andrews, 2002.
Fibonacci Length of Direct Products of Groups 197
9. C. C. Sims, Computation with Finitely Presented Groups, Encyclopedia of Math-
ematics and its Applications 48, Cambridge University Press, Cambridge 1994.
10. D. D. Wall, Fibonacci series modulo
m, Amer. Math. Monthly 67 (1960) 525-532.
11. H. J. Wilcox, Fibonacci sequences of period
n in groups, Fibonacci Quarterly 24
(1986) 356 - 361.