Abstract

In this paper, we study the complexity of p-adic continued fractions of a rational number, which is the p-adic analogue of the Lame’s theorem. We calculate the length of Browkin expansion, and the length of Schneider expansion. Also, some numerical examples have been given.

1. Introduction

It is well known that, in the real case, the sequence of partial quotients of continued fraction expansion of rational number is finite, where the length of this sequence is calculated by Lame's method. In the p-adic case, tow definitions of the continued fractions are given: the first one is the definition of Schneider ¹, and the second is the definition of Ruban ² modified by Brwokin ³. For the expansion of rational number, Browkin ⁴ asked the following question: can every rational number be written as a finite continued fraction? If the answer is "not", determine the infinite continued fractions which correspond to rational numbers.

Based on Schneider definition, Bundschuh ⁵ proved that every rational number has a stationary continued fraction expansion. For Ruban definition, Laohakosol ⁶ and de Weger ⁷ proved that every rational number has a finite or periodic continued fraction expansion. Finally, Browkin based on his definition, proved in ³ that every rational number has a finite continued fraction expansion.

In ⁸ we have studied the complexity of the -adic expansion of a rational number. In the present paper, we give the -adic version of Lamé's theorem, i.e. a boundary of the length of finit expansion of Browkin (see theorem 3.1), we will also give the length of the non-stationary part of the expansion of Schneider (see theorem 3.2).

2. Definitions and Properties

To state our results, we will recall some definitions and basic facts for -adic numbers and continued fractions.

Definition 2.1. Throughout this paper is a prime number, is the field of rational numbers, is the field of nonzero rational numbers and is the field of real numbers. We use to denote the ordinary absolute value, the -adic valuation, the -adic absolute value. The field of -adic numbers is the completion of with respect to the -adic absolute value. Every element of can be expressed uniquely by the -adic expansion with for . In we have simply .

From the -adic expansion of a number we can define another expansion by with for (to get this new expansion just take ). In this case, the -adic fractional part is defined by

(2.1)

and the integer part is defined by . We have .

Definition 2.2. (Browkin continued fraction) From a sequence with values in , we define a sequence of homographic functions of a field or , by and

We call the convergent of this sequence.

A matrix of the homographic function is . Hence, a matrix of the homographic function is

Let us denote it . We have

and , , and , , and

This definition needs the to be nonzero. We mention here that Browkin ^{3, 4} considered the partial quotients in such that and for all in .

For more general criterion of the convergence of Browkin continued fractions, see for example ^{3, 4, 9}.

In the folowing, we give an algorithm for calculating the partial quotients of the -adic continued fractions of a rational number.

Algorithm 2.3. Let , given by the expansion in (2.1)

with , and . We can write in the form , with , , and , . We put

(2.2)

Then the fractional part of is given by . We put again . On the other hand, we have the estimate

We put with and

Now we calculate

Next, we search . Together, we calculate by the formula , with

So, the general forms are as follows

According to Browkin this algorithm is finite. It means that there exists a rank such that for all we have .

To prove the main theorem 3.1, we need the following lemma:

Lemma 2.4. Let a linear recurrent sequence defined by

the following two assertions are verified:

1)

2)

Proof. 1) For all , we have

then

(2.3)

Now, we prove by induction that

For we have Suppose that and we show that Indeed, we have

then the assertion is true for , so is true for all

2) The characteristic polynomial of is given by this polynomial admits two real roots

therefore, the general term of the sequence is given by

(2.4)

so, , because and

Definition 2.5. (Schneinder continued fraction) From a sequence with values in , we define a sequence of homographic functions of a field , for an odd prime number, by and

We call the convergent of this sequence.

A matrix of the homographic function is . Hence, a matrix of the homographic function is

Let us denote it . We have

The sequences and satisfy both the following recurrence

with , and , Moreover, we have and Hence, we have

For general criterion of the convergence of Schneider continued fractions see ^{1, 10}. In the following, we give an algorithm for calculating the partial quotients of the Schneider continued fractions of a rational number.

Algorithm 2.6. Let with , and , , are coprime. We define a sequence by the following steps:

Put

Search and such that the number is an integer, co-prime to and .

Search and such that the number is an integer, co-prime to and .

Thus, we search and such that the number

(2.5)

is an integer, co-prime to and .

We can extract the following formula from the previous

Hence, we have the continued fractions

(2.6)

Using the matrix formula seen before, we obtain the following

We denote by the matrix

Which implies the following recurrence relation

(2.7)

with the initial conditions

so, we have the system

i.e

(2.8)

3. Statements of Main Theorems

For the Brwokin continued fractions we have the following main theorem:

Main Theorem 3.1. Let with Then, the set

is finite, and its cardinal is increased by the real integer part of the number

(3.1)

with are the roots of the equation

Where and are defined as in algorithm 2.3.

For the Schneider continued fractions, Bundschuh ⁵ proved that every rational number has a stationnary expansion, i.e.

In the following main theorem, we will calculate the value of :

Main Theorem 3.2. For let given by its Schneider continued fractions

We assume that , for .

Then, the length of the non-stationary part is equal to

with where , are the roots of the equation .

4. Proof of the Main Theorems

Proof. (Main theorem 3.1)

From lemma 2.4, we have . Therefore

(4.1)

But is a sequence of positive integer numbers, so , for all . This shows that the algorithm for calculating stops after the rank ; hence the set is finite. Now, we prove that

Indeed, from (4.1) we have for all , . On the other hand we have then

In order to have that , it is sufficient to get

Furthermore

(4.2)

So, we take

Example 4.1. For and we have The Table 1 comes from algorithm 2.3

From theorem 3.1, we have then So, the Browkin continued fractions of are given by

Example 4.2. For , and , we put . The Table 2 comes from the algorithm 2.3

From theorem 3.1 we have , then . So, the Browkin continued fractions of are given by

Example 4.3. For the expansion of with the coefficients in are given by

we put . The Table 3 comes from the algorithm 2.3

From theorem 3.1 we have then

So, the Browkin continued fractions of are given by

Proof. (Main theorem 3.2)

In the stationnay case of Schneider continued fractions of rational number, we have If we have for , then

In the next, we suppose , for , the matrix formula becomes

So, we find

(4.3)

Thus

which means and are two linear recurrence sequences. Their general forms are as follows

with the first terms , , , . Moreover, and are the roots of the characteristic equation: they are given by

(4.4)

Back to the formula (4.3), we obtain

we take the ratio of the two numbers, it gives

then

(4.5)

hence

finally

(4.6)

with

it's clear that and , so it is necessary that in order that either well defined. However, we have the following cases:

*) If and or , then .

*) If and or , then .

For and , we have and . We put . The Table 4 comes from the algorithm 2.6

From theorem 3.2 we have , . Then, and So the Schneider continued fractions of are given by

For , and we have and , we put . The Table 5 comes from the algorithm 2.6

From theorem 3.2 we have , . Then and . So, the Schneider continued fractions of are given by

For , and we have and , we put . The Table 6 comes from the algorithm 2.6

From theorem 3.2 we have , . Then and . So, the Schneider continued fractions of are given by

References