1. Introduction
Let and be two positive integers with and be matrices of the group
Denote the group, respectively the semigroup, generated by the matrices
The following problem has been studied in several papers:
Instance:
Question: or are they free with as generators?
Recall that in 1991 D. Klarner, J.-C. Birget and W. Satterfield in [3] proved that if then the problem is not decidable. Moreover in 1999 J. Cassaigne, T. Harju and J. Karhümaki in [4] proved that the same result is true if we suppose that all the matrices are lower triangular.
The case is open and seems difficult. In [5] and [6] results concerning the freeness of the semigroups and groups generated by two matrices are established. In this paper we are studying this problem restricted to the case of Möbius groups.
Let and. The Möbius group is the subgroup of generated by and.
The problem of characterization of the set of complex values of or for which the group is free, was studied in several papers. Thus in [1] it is proved that if is transcendental or then is free.
R.C. Lyndon and J.L. Ullman in [1] remarked that is not free if and only if there exists a word whose letters are non zero integers so that the product of the powers of matrices is a lower triangular matrix. The element in the right upper corner of the matrix is of the form where is a polynomial in of degree with coefficients Moreover are polynomials with integers coefficients in the variables
Results concerning the set of algebraic values of or for which the group is not free were obtained in [1] [2] [7] -[11] .
Deciding if for the group is not free seems very difficult. Let us recall some important results in this direction.
The group is not free if belongs to one of the following sets: (see [1] [2] [7] [8] [10] [11] ).
In this paper we check if for a given there exists a non trivial word of non zero integers such that
The main results of our paper concern the freeness of Möbius groups:
We prove that if the length of is small then the problem is decidable (cases and) (see Theorems 1, 2 and 3).
We give algorithms which solve the problem for (see Corollary 1 and the proof of Theorem 3). Moreover, we give an arithmetical criteria for this problem when (see 2 of Theorem 1).
We give a lower bound numerical function defined from to, increasing and unbounded, such that for each if is a lower triangular matrix then the length of is bigger than (see Theorem 4 and Corollary 3).
As proved by A.F. Beardon ([2] ) in these two cases we have to find solutions for the equations (B1) and (B2). In fact in our paper we consider and study two more general equations:
(B'1)
(B'2)
2. Sequences of Polynomials Associated to Matrices
In this section, we study the properties of some sequences of polynomials in a fixed associated to matrices of the group.
We consider the free monoid of words on non zero integers with the concatenation operation. We denote by the empty word of the free monoid and a non empty word by, where are non zero integers. Then is called the length of and is denoted by. The reversal of a word is and the opposite of is
For every word of of length we consider the matrix product
For instance, for non zero integers we have:
and
We use the notation:
We remark that and are polynomials in with coefficients in We also have and
If then and if then Also and if then
We use the notation to indicate that is a lower triangular matrix or that.
From now on, in order to simplify the notation we write:
For instance, is an abbreviation for the polynomial in with parameters defined by:
Using the fact that we have:
(1)
The sequences of polynomials in, , , and verify the following relations:
(2)
(3)
(4)
(5)
The relations (4) and (5) follow from the equality
In the following sections, we also use the following two relations:
(6)
(7)
Using the previous relations we obtain Proposition 1 The sequences and of polynomials in verify the following identities:
(8)
(9)
Proof. From (5) we have
These identities and the equation give the equation (8). The equation (9) can be similarly obtained .
Let us suppose that where and are non zero integers and.
If the group is not free because in this case (see [1] ).
In the following we consider that. Then, and. Indeed, if then using the fact that we deduce which is in contradiction with the fact that.
This remark allows us to define a new sequence by This sequence satisfies the following relation:
(10)
Thus we obtain
These relations are similar with formulas for continued fractions. The properties of these sequences will be used in the next sections of our paper.
Let us also consider the sequence defined by:
We remark that if and only if
The following lemma is the key element of Section 5.
Lemma 1 Let be non zero integers and suppose that. If
then
Proof. If we have
Let such that is not free. We define the following numerical function:
The number will be called the calibre of the group.
Hence if and only if there are non zero integers such that. Also we have if and only if there are non zero integers such that
3. The Diophantine Equation (B1)
In the next three sections, we consider the following problem, where,:
Instance: Two non zero integers with
Question: Is there a word of length of non zero integers such that
, where?
So we check solutions in non zero integers for the diophantine equation
(11)
The set of for which the Möbius group is not free coincides with the set of for which there exists such that the Equation (11) admits solutions.
In this section, we consider the case and in the next section the case. The relation is equivalent to the Equation (B'1) and the relation is equivalent to the equation (B'2). If and are perfect squares we obtain the equations (B1) and (B2).
We will prove that the problem is decidable. The decidability of the problem has already been established by A.F. Beardon (Theorem 2, [2] ) for the case when and are perfect squares. Our algorithm is simpler and allows us to give an arithmetical criteria for integers and for which the problem has solutions (see Theorem 1 below).
First, we prove a result concerning the equation (B'1).
Proposition 2 Let and be two integers with and. Denote
Then:
1. If and we have
2. The set is finite.
Proof.
1) Let and for put. Then, and.
As we deduce. Because and we have
2) results from
Using the previous proposition we can obtain the decidability of the problem.
Theorem 1 Let and be two integers with. The following sentences are equivalent:
1. The equation has solutions in non zero integers.
2. There exists a divisor of, such that.
3..
Proof. The equivalence between (1) and (2) results from the Proposition 2. It is enough to consider in that proposition. The equivalence between (1) and (3) is obvious.
Remark 1 Let be the set of all divisors of the integer. If is like in (2) of the previous Theorem 1 then a solution to the equation (B'1) can be obtained by taking
• and
• for
where and Moreover any solution of the equation (B'1) can be obtained by this method. We can write as in (3) of the Theorem 1
The results of A.F. Beardon ([2] , theorem 2) concerning the problem for the case when and are perfect squares (or equivalently when) result immediately from the next corollary.
Corollary 1 Let and be two non zero integers with and The group
is not free with the calibre if and only if there exists a divisor of, such that.
From the previous theorem it also follows:
1) The equation (B'1) has no solution if.
2) in the following cases: a); b) ; c) and with
Below we present another form of the Theorem 1 in which we use the decomposition of as a product of prime numbers.
Theorem 2 Let and be two integers with and. Let us suppose that the decomposition of as a product of powers of distinct prime numbers is
Then if and only if there exist:
• two disjoint subsets and of with
• a set of integers with for every
•
such that
Proof. Let be a divisor of We can drop the case because Hence and for every We put and Then and Let:
.
We have for every The condition is equivalent to
Corollary 2 Let and be two non zero integers and be a prime number. Suppose that
Then if and only if there exists an integer with such that
where
Proof. We take in the previous theorem.
Example: Using the previous results and an example from ([7] ) we have and
4. The Beardon Diophantine Equation (B2)
Now we consider the problem. We mention that the equation has been considered in several papers (see [2] [8] [10] ) for the case when and are perfect squares.
From now on, we suppose that for every i.e. following Theorem 1, does not belong to Hence we can define a function by We remark that and a) if
b) if where
Using the relations (8) for the sequence of polynomials we prove that the problem is decidable.
Theorem 3 Let such that does not belong to the set. Then the equation
has a finite number of solutions
Proof. Using the relations (8) we deduce that
Hence Using the function we have:
We obtain a finite number of possibilities for and So and remain to be studied. From the equation
it follows that
Hence there exists such that
Thus there exists a finite number of possibilities for and
If from the inequality we obtain a) If then has no solution.
b) If then
We also remark that the equation (B'2) is equivalent to the following equation
(12)
This enables us to obtain some explicit expressions for the rationals such that equation (B'2) has solutions in
Proposition 3 Let be two non zero integers and be two divisors of If
then the equation (B'2) has solutions in
Proof. Let and Then (10) is equivalent to
Note that if in equation (B'2) we have then is exactly given by the above expression.
Using once again (10) we obtain Proposition 4 Let and be in with If
then the equation (B'2) has solutions in
Proof. Consider (10) for and Then and where It follows that if we take then (10) is verified.
In the next proposition we give another method to obtain solutions of Equation (B'2). It is similar to those presented in [8] and [10] .
Proposition 5 Let and be two integers with Suppose that there exist and
in such that If then the equation (B'2) has solutions in
Proof. Let and Then Hence the equation (B'2) has solutions.
We end this section with the following open questions:
wang#title3_4:spQuestions:
1) Find all the solutions of (B2).
2) Find arithmetical characterizations (similar to those given in Theorem 1 for the positive integers and for which the problem has solutions.
5. Increasing Unbounded Lower Bound Function for (
In this section, we prove that in order to show that the group is not free for a rational with and close to 4, we have to consider longer and longer words in and. Similar remarks (without any proof) have been made by A.F. Beardon in [2] and S.P. Farbman in [7] .
Everywhere in this section, we consider that is a rational number in the open interval.
From the Lemma 1, Section 2, if then For this reason we consider the sequence of rational functions in the variable, defined by:
For example
and
We also define the function by the formula:
Thus one has if and only if, if and only if and if and only if
Now we will calculate.
Note that For this reason we find the matrix, where. We suppose now that with, so. As the matrix verifies the equation:
Using this relation we find that
Hence
Lemma 2 Let, be such that. Then for every we have.
Proof. Since we obtain that. Hence
The previous expression for and Lemma 2 show that is well defined and, for every in the open interval. So is a lower bound numerical function for the function restricted to
Theorem 4 For any and one has if and only if there exists
such that
Proof. Let, where From the definition of the function this previous equality holds if and only if and, for all. But if and only if
Thus we obtain the system of two inequalities and.
Finally, if and only if we have and for all. These inequalities give
Corollary 3 The function is increasing and unbounded.
Therefore
Example: We consider the sequence, for.
• For we have. So, hence. As, it follows that .
• For we have and, , Hence and since
we have
• For we have and, , , , Hence and. From [7] we have.
wang#title3_4:spQuestions:
1) Is it true that for every and, the problem is decidable?
2) Is it true that for every there exists such that the problem is decidable?
3) Is it true that for every there exists, such that the problem has solutions?
4) Find, for.
Acknowledgements
I thank Elias Tahhan (University S. Bolivar, Caracas) and Jerzy Tomasik (Universite d’Auvergne, ClermontFerrand) for discussion concerning some logical aspects of my paper.