Abstract

Let and be two fixed non zero integers verifying the condition. We check solutions in non zero integers and for the following Diophantine equations: (B1) (B2) The equations (B1) and (B2) were considered by R.C. Lyndon and J.L. Ullman in [1] and A.F. Beardon in [2] in connection with the freeness of the Möbius group generated by two matrices of namely and where They proved that if one of the equations (B1) or (B2) has solutions in non zero integers then the group is not free. We give algorithms to decide if these equations admit solutions. We obtain an arithmetical criteria on and for which (B1) admits solutions. We show that for all and the equations (B1) and (B2) have only a finite number of solutions.

Keywords:Diophantine Equation, Möbius Groups, Free Group

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.

References