CONTINUED FRACTIONS, THE GROUP GL(2, ℤ), AND PISOT NUMBERS

V.N. BERESTOVSKII, YU.G. NIKONOROV

Abstract. We use subsemigroups of the group of invertible integer matrices to prove some properties of continued fractions, generalized golden sections, generalized Fibonacci and Lucas numbers. Some properties of special recurrent sequences are studied. Connections between continued fractions and Pisot numbers are investigated. We suggest also some unsolved problems.

Introduction

In this paper we investigate interconnections between continued fractions, some subsemigroups of the group GL(2, ℤ), and Pisot numbers. The main tool of this investigation is the matrix calculus which permits from the author’s point of view to explain interconnections between these notions much better. Obtained structural results on subsemigroups of the group GL(2, ℤ) are used to study properties of generalized Fibonacci and Lucas numbers. Also we formulate some unsolved problems in the paper.

The paper is divided into eight sections. In the first section we give a necessary information on continued fractions and corresponding matrices, investigate some properties of these matrices. In the second section we discuss Pisot numbers, polynomials and matrices, prove some results on Pisot polynomials. In the third section we prove a series of results on recurrent sequences. On this ground we give a new proof of the classical Pisot-Vijayaraghavan theorem in the fourth section. Some properties of subsemigroups of the group GL(2, ℤ), connected with continued fractions and Pisot numbers, are investigated in the fifth section. In the sixth section we study asymptotic properties of sequences of linear-fractional transformations, corresponding to infinite continued fractions. In the seventh section we find some relations between the entries of natural powers of (2 × 2)-matrices. The last, eighth section, is devoted to an investigation of properties of generalized golden sections, Fibonacci and Lucas numbers. Let us remark that (generalized) golden sections are Pisot numbers.

In the course of the article we use the notation ℚ, ℝ, and ℂ for the sets of rational, real, and complex numbers respectively. We denote by ℤ and ℤ_{+} the sets of integer rational numbers and nonnegative integer rational numbers respectively. The set of natural numbers is denoted by the symbol ℕ (we have in mind that ℕ = ℤ_{+} \ {0}). The symbol {u_{k}} will denote a sequence, indexed by numbers from ℤ_{+}. By A^{t} we denote the transposition of a matrix A, and by tr(B) we denote the trace of the matrix or the operator B. Another notation is explained in the corresponding parts of the text.

2000 Mathematical Subject Classification: 11A55, 11B39, 11J70, 11R06, 20H05, 20M20.

Key words and phrases: continued fractions, Pisot numbers, recurrent sequences, generalized Fibonacci and Lucas numbers.

The first author was supported by RFBR (grant No. 02-01-00192-a). The second author was supported by the Council on leading scientific schools of Russian Federation (grant No. 311.2003.1), RFBR (grant No.

02-01-01071), and the Russian Ministry of Education (grant No. E 02-1.0-120).

1. Continued fractions and matrices generated by them

A simplest (regular) continued fraction is an expression of the form

q_{0} + \frac{1}{q_{1} + \frac{1}{q_{2} + ...}}  (1)

corresponding to a finite or an infinite sequence q_{n}, 0 ≤ n < ω + 1, where q_{0} is an integer number, while q_{1}, q_{2}, … are natural numbers; in the case 0 < ω < +∞ one suppose that q_{ω} ≥ 2. If ω < +∞, then the fraction (1) has quite definite value, denoted by the symbol [q_{0}; q_{1}, q_{2}, …, q_{ω}]. It is known [21] that in the case of infinite sequence there is a finite limit

[q_{0}; q_{1}, q_{2}, …] := lim_{n→∞}[q_{0}; q_{1}, …, q_{n}].  (2)

Here the initial segment q_{0}, q_{1}, …, q_{n} of a finite or an infinite sequence q_{0}, q_{1}, q_{2}, … defines the n-th convergent (of continued) fraction

\frac{P_{n}}{Q_{n}} := [q_{0}; q_{1}, …, q_{n}]  (3)

of the number [q_{0}; q_{1}, …]; the numerator and the denominator of the fraction on the left are supposed to be coprime integer numbers with a positive denominator. On the ground of the Leibnitz convergent criterion for alternating series and formulas (4), (13) it follows easily the existence of the limit (2) and the fact that this limit lies between every two consequent convergent fractions. Conversely [21], any real number r is uniquely represented in the form of the fraction (1), where numbers q_{n} are successive non-complete quotients of the pair (r, 1) by analogy with the Euclidean algorithm for a pair of natural numbers. Thus, there is oneto-one correspondence between real numbers and regular continued fractions of the form (1), which simultaneously with their value (2) are denoted by the symbol [q_{0}; q_{1}, q_{2}, …].

One can read on continued fractions and their generalizations in books and papers [1], [2], [3], [4], [5], [8], [10], [12], [17], [19], [21], [22], [23], [31], [36], [38]. A simple geometric construction of convergent (and closely related with them intermediate) fractions of a given real number as vertices (respectively, integer valued points in the interior of sides) of socalled Klein polygons is given in the book [15]; there is also a picture of this construction for golden section there. Continued fractions have various applications. Connections of Pell equations with continued fractions are considered in [6]. It follows easily from the Klein construction mentioned above that convergent (sometimes intermediate) fractions are the best approximations for a given number among all rational numbers with a given upper bound for denominators. This fact is applied in music (the creation of nowadays existing the logarithmically uniform musical scale with twelve tones by German scientist and musician Andreas Werkmeister about 1700 year, which was rejected by D. Diderot and was supported by ”Well tempered clavier” of J.S. Bach, see [9], [24]) and in astronomy [13]. In the book [20] the moment problem is solved with the help of functional continued fractions.

One can write well-known recurrent formulas

P_{n+1} = q_{n+1}P_{n} + P_{n−1}, Q_{n+1} = q_{n+1}Q_{n} + Q_{n−1}  (4)

for numerators and denominators of convergent fractions in the following matrix form

(\begin{matrix}P_{n} & Q_{n} \\ P_{n+1} & Q_{n+1} \end{matrix}) = (\begin{matrix}0 & 1 \\ 1 & q_{n+1} \end{matrix}) (\begin{matrix}P_{n−1} & Q_{n−1} \\ P_{n} & Q_{n} \end{matrix}) .  (5)

Continued fractions of the form (1) with q_{0} ≥ 1 or non-finishing by q_{0} if q_{0} = 0 (with the reserve mentioned above in the case of a finite fraction) represent all positive numbers (in the interval (0, 1), if q_{0} = 0). We suppose that these conditions are satisfied in what follows. Then it is convenient to suppose that

(\begin{matrix}P_{−1} & Q_{−1} \\ P_{0} & Q_{0} \end{matrix}) = (\begin{matrix}1 & 0 \\ q_{0} & 1 \end{matrix}) .  (6)

For natural numbers q, q_{1}, …, q_{n}, we introduce the notation

M(q) := (\begin{matrix}0 & 1 \\ 1 & q \end{matrix}); N(q) := (\begin{matrix}1 & 0 \\ q & 1 \end{matrix}) ,  (7)
M(q_{1}, …, q_{n}) := M(q_{n}) … M(q_{1}).  (8)

Evidently,

|\begin{matrix}0 & 1 \\ 1 & q \end{matrix}| = −1, |\begin{matrix}1 & 0 \\ q & 1 \end{matrix}| = 1.  (9)

It follows from formulas (5), (6), (7), and (9) that, under condition n ≥ 0,

(\begin{matrix}P_{n} & Q_{n} \\ P_{n+1} & Q_{n+1} \end{matrix}) = M(q_{n+1}) … M(q_{1}) when q_{0} = 0,  (10)
(\begin{matrix}P_{n} & Q_{n} \\ P_{n+1} & Q_{n+1} \end{matrix}) = M(q_{n+1}) … M(q_{1})N(q_{0}), when q_{0} ≥ 1,  (11)
|\begin{matrix}P_{n} & Q_{n} \\ P_{n+1} & Q_{n+1} \end{matrix}| = P_{n}Q_{n+1} − Q_{n}P_{n+1} = (−1)^{n+1},  (12)

i.e. matrices (10) and (11) (with nonnegative entries) are contained in the group GL(2, ℤ) of all nondegenerate integer (2 × 2)-matrices, and the well-known formula for the difference of successive convergent fractions is fulfilled:

\frac{P_{n}}{Q_{n}} − \frac{P_{n+1}}{Q_{n+1}} = \frac{(−1)^{n+1}}{Q_{n}Q_{n+1}} .  (13)

By transposing the matrix (10) and using relations (3) and (7), we get, as a corollary of symmetry of the matrix M(q), the equality

\frac{Q_{n}}{Q_{n+1}} = [0; q_{n+1}, …, q_{1}].  (14)

Definition 1. We shall say that a (2 × 2)-matrix is non-decreasing by rows (columns), if the difference of the second and the first columns (respectively, of the second and the first rows) is a vector-column (vector-row) with nonnegative coordinates. Analogously we define a matrix which is non-increasing by rows (columns).

The main result of this section is

Theorem 1. An integer matrix

Z := (\begin{matrix}z_{11} & z_{12} \\ z_{21} & z_{22} \end{matrix})

with nonnegative entries is a matrix of the form (10) or (11) with the uniquely determined natural numbers q_{0}, q_{1}, ..., q_{n+1} if and only if the matrix Z is non-decreasing by columns and z_{11}z_{22} − z_{12}z_{21} = ±1. Moreover, the matrix Z has the form (10) if and only if it is non-decreasing by rows also.

Remark 1. The last statement of this theorem has been proved in the paper [34].

Remark 2. Conditions of Theorem 1 have simple geometric sense:

1) Every vector-column (and vector-row in the last case) of the matrix lies in the octant 0 ≤ x ≤ y;

2) Vector-columns (or vector-rows) of the matrix constitute a basis of integer lattice on the plane x, y over the ring of integer numbers.

Matrices and facts indicated here are used further for simple proofs of some properties of continued fractions and generalized golden sections and also Fibonacci and Lucas numbers.

Proof of Theorem 1. Let us prove at first the necessity. The unimodularity of matrices under consideration (i.e. the property 2) of Remark 2) follows from (9). The property 1) of Remark 2 for vector-columns of a matrix follows immediately from the formula (4). Then the same property for vector-rows of a matrix of the form (10) is obtained by transposing of this matrix and with using the well-known rule for transposition of a matrix product and, also, a symmetry of the matrices M(q).

Let us prove the sufficiency by induction on the nonnegative number k = k(Z) = z_{11}z_{12}. Let suppose that the integer (2×2)-matrix Z is unimodular and non-decreasing by columns. Let k = 0. Then two cases are possible.

A) z_{11} = 0. Then z_{12} = z_{21} = 1 and Z = M(z_{22}).

B) z_{12} = 0. Then z_{11} = z_{22} = 1 and Z = N(z_{21}).

Evidently, in these cases the representation of the matrix in the form (10) or (11) is unique.

Let suppose that for all matrices with 0 ≤ k < l the statement is proved and k(Z) = k = l. Obviously, all entries of the matrix Z are positive and at least one of inequalities z_{11} ≤ z_{21}, z_{12} ≤ z_{22} is strong.

Set q = min([z_{21}/z_{11}], [z_{22}/z_{12}]), where by [α] we denote the integer part of a number α. Evidently, q ≥ 1. Let us consider the matrix

Z′ = M(q)^{−1}Z = (\begin{matrix}−q & 1 \\ 1 & 0 \end{matrix}) Z = (\begin{matrix}z_{21} − qz_{11} & z_{22} − qz_{12} \\ z_{11} & z_{12} \end{matrix}) .

It follows from the definition of the number q that all entries of the matrix Z′ are nonnegative, moreover, at least one of inequalities

1) z′_{12} < z′_{22}, or 2) z′_{11} < z′_{21}.

is fulfilled. In the first case we have z′_{11} ≤ z′_{21}. Otherwise

|detZ′| ≥ (z_{21} − qz_{11})z_{12} − z_{11}(z_{22} − qz_{12}) ≥
(z_{11} + 1)(z_{22} − qz_{12} + 1) − z_{11}(z_{22} − qz_{12}) ≥ z_{11} + 1 ≥ 2,

what is impossible in view of unimodularity of the matrix Z′. In the second case we must have z′_{12} ≤ z′_{22}. Otherwise

|detZ′| ≥ (z_{22} − qz_{12})z_{11} − z_{12}(z_{21} − qz_{11}) ≥
(z_{12} + 1)(z_{21} − qz_{11} + 1) − z_{12}(z_{21} − qz_{11}) ≥ z_{12} + 1 ≥ 2,

what is impossible. Thus the matrix Z′ is unimodular, non-decreasing by columns, and consists of nonnegative entries, furthermore k(Z′) < k(Z) because one of conditions 1) or 2) is satisfied. Then by the inductive assumption, Z′ is uniquely represented as the product (10) or (11). Therefore, the matrix Z = M(q)Z′ is also represented in the form (10) or (11). The uniqueness of such representation follows from the fact that for a natural q_{1} and the matrix Z_{1} = M(q_{1})^{−1}Z, at least one of its entries is negative if q_{1} > q; if q_{1} < q, then for the matrix Z_{1} the condition of non-decreasing by columns is false.

If the matrix Z ∈ GL(2, ℤ) is non-decreasing by columns and rows simultaneously, then by the proved above, it is uniquely represented in the form of the product (10) or (11). Moreover, the last variant is impossible. Otherwise the transposed matrix Z^{t} is represented in the form of the product

Z^{t} = N(q_{0})^{t}M(q_{n+1}) … M(q_{1}), q_{0} ≥ 1.

Hence the matrix Z^{t} is not non-decreasing by columns, which is impossible. The theorem is proved.

2. Pisot numbers, polynomials, and matrices

In this section we consider some facts, connected with one special class of real numbers, namely, Pisot numbers. Besides an account of a part of the classical theory, we prove also some new results, which have an independent interest and are necessary for further presentations.

Definition 2. An integer algebraic number λ > 1 is called a Pisot number if all its conjugates, different from λ, lie in the open disc |z| < 1 on the complex plane.

We note that Pisot numbers are also called Pisot-Vijayaraghavan or P-V numbers. The foundations of the theory of these numbers have been established in papers of Ch. Pisot (1910-1984), T. Vijayaraghavan (1902-1955), and R. Salem (1898-1963). A classical presentation of this theory one can find in books [14] and [26].

Later on we shall need also the following two definitions.

Definition 3. A polynomial f(z) = z^{n} + a_{n−1}z^{n} + ⋯ + a_{1}z + a_{0} with integer rational coefficients is called a Pisot polynomial, if it is irreducible and one of its roots η has the property that η or −η is a Pisot number.

It is clear that any Pisot number η is a root of the unique Pisot polynomial f(z), because every common root of two polynomials with rational coefficients is also a root of their greatest common divisor. Moreover, the number −η is a root of another Pisot polynomial f̃(z) = (−1)^{deg f(z)}f(z). Thus there is an evident one-to-one correspondence between Pisot numbers and pairs of Pisot polynomials.

Definition 4. A square matrix A with integer rational entries is called a Pisot matrix, if its characteristic polynomial is a Pisot polynomial.

Every Pisot polynomial is characteristic polynomial of some (non-unique) Pisot matrix. This follows, for example, from Lemma 3 below.

The significance of Pisot numbers in the theory of diophantine approximations one can see from results below. For a real number y, we shall denote by ∥y∥ the distance from y to a nearest integer number, i.e.

∥y∥ = min{|y − k| | k ∈ ℤ}.

Some information on the arithmetic nature of a real number λ > 1 one can obtain by the investigation of asymptotic properties of the sequences {aλ^{n}}, n ∈ ℤ_{+}, for various real numbers a.

Definition 5. For a real number λ > 1, by a Pisot set of this number we mean the set

P_{λ} = {a ∈ ℝ | ∥aλ^{n}∥ → 0, n → ∞}.

For a given algebraic number λ, we consider the finite extension ℚ(λ) of the field ℚ and denote by Tr(y) algebraic trace of a number y ∈ ℚ(λ), i.e. the trace of the linear map x → x · y in the linear space ℚ(λ) over the field ℚ ([7], Chapter VI, §47). An effective way for calculating of this trace is indicated in Lemma 7.

Theorem (Pisot-Vijayaraghavan). An algebraic number λ > 1 is a Pisot number if and only if P_{λ} ≠ {0}. In this case

P_{λ} = {a ∈ ℚ(λ) | Tr(aλ^{n}) ∈ ℤ for sufficiently large n}.

Thus, this theorem gives a complete description of algebraic numbers λ > 1 with the set P_{λ} ≠ {0}.

In 1935 J.F. Koksma [32] had shown that for almost all numbers λ > 1, the sequence {λ^{n}} is uniformly distributed by (mod 1) (about uniformly distributed sequences see, for example, [10]). Pisot numbers λ > 1 in view of the theorem above (which have been proved in the pioneer work [37]) are exceptional in this sense, because one can easily prove that 1 ∈ P_{λ} (see the proof of the Pisot-Vijayaraghavan theorem in the section 4).

It is interesting the following

Question 1 (Ch. Pisot). Are there transcendental numbers λ > 1 with the set P_{λ} ≠ {0}?

Some results in this direction have been established by Ch. Pisot himself and others [14, 26]. Nevertheless, there is no final answer to this question up to now.

It is appropriate to give here three astonishing characterizations of Pisot numbers, which are not connected with any algebraic condition.

The first one is connected with the harmonic analysis. A subset E ⊂ (0, 1) is called a set of uniqueness (for a trigonometric series), if condition

\frac{a_{0}}{2} + ∑_{n=1}^{∞}(a_{n} cos 2πnx + b_{n} sin 2πnx) = 0, x ∈ (0, 1), x ∉ E,

for an ordinary trigonometric series with real coefficients implies that a_{n} = b_{n} = 0 for all n. For a real number λ > 2, consider (generalized) Cantor set (of measure zero)

E_{λ} := {x = (λ − 1) ∑_{k=1}^{∞} ε_{k}λ^{−k} | ε_{k} = 0, 1} .

In the case λ = 3 one get the famous Cantor set. The Salem-Zigmund theorem in [26] states that the set E_{λ} is a set of uniqueness if and only if λ is a Pisot number.

The second characterization is connected with numbers represented by polynomials of the number λ with bounded integer nonnegative coefficients. For a natural number k denote by 0 =: y_{0}^{(k)} < y_{1}^{(k)} < … an increasing sequence of all real numbers y, which admit a representation of the form

y = ε_{1}λ + ⋯ + ε_{i}λ^{i}; i ≥ 1; ε_{1}, …, ε_{i} ∈ {0, 1, …, k}.

Next we define the difference sequence of these numbers u_{n}^{(k)} := y_{n+1}^{(k)} − y_{n}^{(k)}, n ≥ 0. Theorem 1 in [29] states that a real number λ ∈ (1, 2) is a Pisot number if and only if lim_{\overline{n→∞}} u_{n}^{(k)} > 0 for all natural numbers k.

The third characterization is connected with the finite automaton theory. Let us given a real number λ, a natural number c, and set of integer numbers C = {−c, …, 0, …, c}. Consider set Z(λ, c) of infinite words in C^{ℤ_{+}}, corresponding to 0, i.e.

Z(λ, c) = {s = {s_{n}}_{n≥0} ∈ C^{ℤ_{+}} | ∑_{n=0}^{∞} s_{n}λ^{−n} = 0} .

It is proved in paper [25] that the number λ is a Pisot number if and only if the set Z(λ, c) is recognizable by a finite automaton for every natural number c.

The structure of the set S of all Pisot numbers at this time is thoroughly investigated [26]. By the R. Salem theorem, the set S is closed [14]. It is proved in paper [27] that

the order type of the set S is the ordered sum ∑_{n=1}^{∞} a_{n}, where a_{1} = ω + 1 + ω^{∗}, and by

induction, a_{n+1} = a_{n}ω + 1 + (a_{n}ω)^{∗}. The smallest Pisot number θ is a positive root of the equation z^{3} − z − 1 = 0. Nevertheless, there are many unsolved problems, connected with Pisot numbers. For example, there is no convenient criterion, which permits to define by coefficients of some polynomial, whether it is a Pisot polynomial or not. We prove some results in this direction.

We associate with arbitrary Pisot polynomial f(z) = z^{n} + a_{n−1}z^{n−1} + ⋯ + a_{1}z + a_{0} the vector (a_{0}, a_{1}, …, a_{n−1}) ∈ ℤ^{n}. Thus, the set of Pisot polynomials of degree n corresponds to some subset of vectors in ℤ^{n}, which we denote by P(n). Further we shall describe sets P(2) and P(3).

By symbols ℜ(z) and ℑ(z) we shall denote respectively the real and the imaginary parts of a complex number z ∈ ℂ, the symbol sign(x) denotes the sign of a number x ∈ ℝ.

Lemma 1. A polynomial f(z) = z^{n} + a_{n−1}z^{n−1} + ⋯ + a_{1}z + a_{0} with integer rational coefficients is a Pisot polynomial if and only if a_{0} ≠ 0 and f(z) has one root in the set |z| > 1 and n − 1 roots in the disc |z| < 1.

Proof. If f(z) is a Pisot polynomial, then it is irreducible over the field of rational numbers, in particular, a_{0} ≠ 0. Moreover, one of its roots λ (|λ| is Pisot number) is greater than 1 by its absolute value. By definition of Pisot number, the roots of f(z), which are not equal to λ, lie in the disc |z| < 1.

Suppose now that the polynomial f(z) has one root in the set |z| > 1 and n − 1 roots in the disc |z| < 1, and besides this, a_{0} ≠ 0. We shall show that f(z) is a Pisot polynomial. For this it’s enough to show that f(z) is irreducible over the field ℚ. Really, if f(z) is irreducible, then the absolute value of its unique root lying in the set |z| > 1, is a Pisot number. By the condition of the lemma f(0) = a_{0} ≠ 0, hence all roots of the polynomial f(z) are not equal to 0. Recall that every polynomial with integer rational coefficients is irreducible over rational numbers if and only if it is irreducible over integer numbers ([7], Chapter V, §30). Let f(z) = f_{1}(z) · f_{2}(z), where f_{i}(z) have integer coefficients. Evidently, absolute values of older coefficients of these polynomials are equal to 1. Since one of polynomials f_{i}(z) has only roots z_{k} such that 0 < |z_{k}| < 1, then its constant term is not an integer number.

Theorem 2. A polynomial f(z) = z^{n} + a_{n−1}z^{n} + ⋯ + a_{1}z + a_{0} with integer rational coefficients is a Pisot polynomial if and only if a_{0} ≠ 0 and polynomial

g(t) = b_{n}t^{n} + b_{n−1}t^{n−1} + ⋯ + b_{1}t + b_{0} = (t − 1)^{n}f (\frac{t + 1}{t − 1})

with integer rational coefficients has one root in the half-plane ℜ(t) > 0 and n − 1 roots in the half-plane ℜ(t) < 0.

Proof. The linear-fractional map z = F (t) = \frac{t+1}{t−1} is an involution on the extended complex plane and translates sets ℜ(t) < 0 and ℜ(t) > 0 to sets |z| < 1 and |z| > 1 respectively.

Now let f(z) = z^{n} + a_{n−1}z^{n} + ⋯ + a_{1}z + a_{0} be a Pisot polynomial. According to Lemma 1, the condition a_{0} ≠ 0 is fulfilled. Furthermore, f(z) has n − 1 roots in the disc |z| < 1, and one root (whose absolute value is a Pisot number) in the set |z| > 1. Taking into account properties of the map F, we obtain that the polynomial

g(t) = (t − 1)^{n}f (\frac{t + 1}{t − 1})

has one root in the half-plane ℜ(t) > 0 and n − 1 roots in the half-plane ℜ(t) < 0.

Let us prove the converse statement. If the polynomial g(t) has one root in the half-plane ℜ(t) > 0 and n − 1 roots in the half-plane ℜ(t) < 0, then taking one more into account properties of the map F, we get that the polynomial f(z) has one root in the set |z| > 1 and n − 1 roots in the disc |z| < 1. Besides this, a_{0} ≠ 0, therefore, by Lemma 1, f(z) is a Pisot polynomial.

The theorem mentioned above gives an effective tool for searching Pisot polynomials, because the problem of finding the quantity of complex roots of the polynomial g(t), satisfying the condition ℜ(t) > 0 (and condition ℜ(t) < 0, if we apply involutive substitution s = −t), is well-known, and is solved by classical Routh-Hurwitz theorem ([11], Chapter XVI). Let us apply Theorem 2 for a description of Pisot polynomials of degrees 2 and 3.

Theorem 3. Let us consider the set

P(2) = {(p, q) ∈ ℤ^{2} | f(z) = z^{2} + pz + q is a Pisot polynomial}.

Then

P(2) = {(p, q) ∈ ℤ^{2} | |p| > |q + 1|, q ≠ 0}.

Proof. According to Theorem 2, a polynomial f(z) = z^{2} + pz + q is a Pisot polynomial if and only if q ≠ 0, and the polynomial

g(t) = (t − 1)^{2}f (\frac{t + 1}{t − 1}) = (1 + p + q)t^{2} + (2 − 2q)t + (1 − p + q)

has one root in both half-planes ℜ(t) > 0 and ℜ(t) < 0. But the last condition is equivalent to the inequality (1 + p + q)(1 − p + q) < 0, whence we get the statement of the theorem.

Theorem 4. Let us consider the set

P(3) = {(p, q, r) ∈ ℤ^{3} | f(z) = z^{3} + pz^{2} + qz + r is a Pisot polynomial}.

Then P(3) = M_{1} ∪ M_{2} ∪ M_{3}, where

M_{1} = {(p, q, r) ∈ ℤ^{3} | p = 3r, q = 3, |r| > 1},
M_{2} = {(p, q, r) ∈ ℤ^{3} | (1 + p + q + r)(3 − p − q + 3r) < 0, |p + r| > |q + 1|, r ≠ 0},

M_{3} = {(p, q, r) ∈ ℤ^{3} | (1+p+q+r)(3−p−q+3r) > 0, |p+r| > |q+1|, 1−q+pr−r^{2} > 0, r ≠ 0}.

One could prove the stated theorem with the help of the Routh-Hurwitz theorem, but we shall prove it by using the Cauchy index for rational real-valued functions ([11], Chapter XVI).

For every real-valued rational function R(x), there is the expansion ([7], Chapter V, §36):

R(x) = ∑_{k=1}^{p} ∑_{l=1}^{n_{k}} \frac{A_{l}^{k}}{(x − α_{k})^{l}} + R_{1}(x),  (15)

where α_{k} are real poles of the function R(x), n_{k} is the degree of the pole α_{k} (1 ≤ k ≤ p), A_{l}^{k} are some real numbers, and R_{1}(x) is some rational function without real poles.

The Cauchy index of a real-valued rational function between limits −∞ and +∞ is defined by the formula

I_{−∞}^{+∞}R(x) := ∑_{k=1}^{p} ∑_{l=1}^{n_{k}} \frac{1 − (−1)^{l}}{2} sign(A_{l}^{k}).  (16)

Let suppose that the polynomial

g(t) = b_{n}t^{n} + b_{n−1}t^{n−1} + ⋯ + b_{1}t + b_{0}, b_{l} ∈ ℝ, 0 ≤ l ≤ n,

has no roots in the imaginary axis ℜ(t) = 0 and has k roots in the half-plane ℜ(t) > 0. Then the following formula is fulfilled ([11], Chapter XVI, §3):

I_{−∞}^{+∞}R(ω) = n − 2k, where R(ω) = \frac{g_{2}(ω)}{g_{1}(ω)},  (17)

while g_{1}(ω) and g_{2}(ω) are polynomials with real coefficients, defined by the equality

\frac{1}{i^{n}} g(iω) = g_{1}(ω) − ig_{2}(ω), i = \sqrt{−1}.

With usage of the formula (17), we shall prove the following auxiliary statement.

Lemma 2. A polynomial g(t) = b_{3}t^{3} + b_{2}t^{2} + b_{1}t + b_{0}, where b = (b_{0}, b_{1}, b_{2}, b_{3}) ∈ ℝ^{4}, has 1 root in the half-plane ℜ(t) > 0 and 2 roots in the half-plane ℜ(t) < 0 if and only if b ∈ M̃_{1} ∪ M̃_{2} ∪ M̃_{3}, where

M̃_{1} = {b ∈ ℝ^{4} | b_{1} = 0, b_{2} = 0, b_{0}b_{3} < 0},
M̃_{2} = {b ∈ ℝ^{4} | b_{1}b_{3} < 0, b_{0}b_{3} < 0},
M̃_{3} = {b ∈ ℝ^{4} | b_{1}b_{3} > 0, b_{0}b_{3} < 0, b_{1}b_{2} − b_{0}b_{3} > 0}.

Proof. If the polynomial g(t) = b_{3}t^{3} +b_{2}t^{2} +b_{1}t+b_{0} has 1 root in the half-plane ℜ(t) > 0 and 2 roots in the half-plane ℜ(t) < 0, then b_{3} ≠ 0 and g(t) has no roots in the imaginary axis ℜ(t) = 0. Let

g_{1}(ω) = b_{3}ω^{3} − b_{1}ω, g_{2}(ω) = b_{2}ω^{2} − b_{0}.

It is clear that

i · g(iω) = g_{1}(ω) − ig_{2}(ω), where i = \sqrt{−1}.

The polynomial g(t) has a root in the imaginary axis ℜ(t) = 0 if and only if polynomials g_{1}(ω) and g_{2}(ω) have a common real root. It is easily to see that considered polynomials have a common root ω = 0 if and only if b_{0} = 0. Let us assume that they have a common real root ω ≠ 0. Hence the polynomial g_{3}(ω) = b_{3}ω^{2} − b_{1} has the same root. Since b_{3} ≠ 0, then polynomials g_{2}(ω) and g_{3}(ω) have a common (maybe, complex) root if and only if their resultant Res(g_{2}, g_{3}) is equal to 0 ([7], Chapter V, §34). Direct calculations show that Res(g_{2}, g_{3}) = (b_{1}b_{2} − b_{0}b_{3})^{2}. In order that the common root ω ≠ 0 of the polynomials g_{1}(ω) and g_{2}(ω) will be real in addition it is necessary and sufficient that the condition b_{1}b_{3} > 0 is satisfied. Thus the polynomial g(t) has no purely imaginary root if and only if the following two conditions are satisfied:

1) b_{0} ≠ 0 and 2) b_{1}b_{2} − b_{0}b_{3} ≠ 0 when b_{1}b_{3} > 0.

According to the formula (17), the polynomial g(t) (when it has no roots on imaginary axis) has exactly one root on the half-plane ℜ(t) > 0 if and only if the equality

I_{−∞}^{+∞} \frac{g_{2}(ω)}{g_{1}(ω)} = 1 ,

is fulfilled, which, in turn, is equivalent to the equality

I_{−∞}^{+∞}R(ω) = sign(b_{3}) , where R(ω) = \frac{b_{2}ω^{2} − b_{0}}{ω(ω^{2} − L)}, L = b_{1}/b_{3}.  (18)

Next we consider successively next three cases: L = 0, L < 0 and L > 0.

The equality L = 0 is equivalent to b_{1} = 0. The condition that the polynomial g(t) has no purely imaginary roots is equivalent in this case to the inequality b_{0} ≠ 0. It is clear that

R(ω) = \frac{b_{2}ω^{2} − b_{0}}{ω(ω^{2} − L)} = \frac{b_{2}ω^{2} − b_{0}}{ω^{3}} = \frac{b_{2}}{ω} − \frac{b_{0}}{ω^{3}} ,

Hence the equality (18) is equivalent in this case to the equation

sign(b_{2}) − sign(b_{0}) = sign(b_{3}) .

The last equation is fulfilled if and only if b_{2} = 0 and b_{0}b_{3} < 0. Thus in the case L = 0 the polynomial g(t) has 1 root in the half-plane ℜ(t) > 0 and 2 roots in the half-plane ℜ(t) < 0 if and only if

b ∈ {b ∈ ℝ^{4} | b_{1} = 0, b_{2} = 0, b_{0}b_{3} < 0}.

The inequality L < 0 is equivalent to b_{1}b_{3} < 0. The condition that the polynomial g(t) has no purely imaginary roots, as well as in the previous case, is equivalent to the inequality b_{0} ≠ 0. It is not difficult to get the expansion

R(ω) = \frac{b_{2}ω^{2} − b_{0}}{ω(ω^{2} − L)} = \frac{b_{0}/L}{ω} + R_{1}(ω) ,

where R_{1}(ω) is a rational function without real poles. Therefore, the equality (18) is equivalent in this case to the equation

sign (\frac{b_{0}}{L} ) = − sign(b_{0}) = sign(b_{3}) .

The last equality is satisfied if and only if b_{0}b_{3} < 0. Consequently, in the case L < 0 the polynomial g(t) has 1 root in the half-plane ℜ(t) > 0 and 2 roots in the half-plane ℜ(t) < 0 if and only if

b ∈ {b ∈ ℝ^{4} | b_{0}b_{3} < 0}.

Now consider the case L > 0, which is equivalent to b_{1}b_{3} > 0. The condition that the polynomial g(t) has no purely imaginary root is equivalent to the fulfillment of the next two inequalities: b_{0} ≠ 0 and b_{1}b_{2} − b_{0}b_{3} ≠ 0. Let L = s^{2}, where s > 0. Direct calculations show that

R(ω) = \frac{b_{2}ω^{2} − b_{0}}{ω(ω^{2} − L)} = \frac{A_{1}}{ω} + \frac{A_{2}}{ω − s} + \frac{A_{3}}{ω + s}, where A_{1} = b_{0}/L, A_{2} = A_{3} = \frac{b_{2}L − b_{0}}{2L} .

Therefore, the equality (18) in the case L > 0 is equivalent to the equation

sign(b_{0}) + 2 sign(b_{2}L − b_{0}) = sign(b_{3}) .

This equation is satisfied if and only if we have two inequalities:

b_{0}b_{3} < 0 and (b_{2}L − b_{0})b_{3} = b_{2}b_{1} − b_{0}b_{3} > 0.

Consequently, in the case L > 0 the polynomial g(t) has 1 root in the half-plane ℜ(t) > 0 and 2 roots in half-plane ℜ(t) < 0 if and only if

b ∈ {b ∈ ℝ^{4} | b_{0}b_{3} < 0, b_{1}b_{2} − b_{0}b_{3} > 0}.

Combining three cases, considered above, we obtain the statement of the lemma.

Proof of Theorem 4. According to Theorem 2, the polynomial f(z) = z^{3} +pz^{2} +qz +r with integer rational coefficients is a Pisot polynomial if and only if r ≠ 0 and the polynomial

g(t) = (t − 1)^{3}f (\frac{t + 1}{t − 1}) = b_{3}t^{3} + b_{2}t^{2} + b_{1}t + b_{0} =

= (1 + p + q + r)t^{3} + (3 + p − q − 3r)t^{2} + (3 − p − q + 3r)t + (1 − p + q − r)

has one root in the half-plane ℜ(t) > 0 and 2 roots in the half-plane ℜ(t) < 0. Now it is sufficient to apply Lemma 2 to get the required result. Note only that under assumption of the theorem equalities b_{1}b_{3} = (3−p−q +3r)(1+p+q +r) and b_{1}b_{2} −b_{0}b_{3} = 8(1−q +pr−r^{2}) are fulfilled, while the inequality b_{0}b_{3} = (1+q)^{2} −(p+r)^{2} < 0 is equivalent to the inequality |p + r| > |q + 1|. Moreover, conditions b_{1} = b_{2} = 0 and b_{0}b_{3} < 0 are satisfied if and only if q = 3, p = 3r and |r| > 1.

The following theorem gives an easily verified sufficient criterion for Pisot polynomials of higher degrees.

Theorem 5. Let suppose that for the polynomial f(z) = z^{n} + a_{n−1}z^{n−1} + ⋯ + a_{1}z + a_{0} with integer rational coefficients the inequalities

|a_{n−1}| > 1 + ∑_{k=0}^{n−2} |a_{k}|, a_{0} ≠ 0

are fulfilled. Then f(z) is a Pisot polynomial.

Proof. We shall prove the theorem with the help of the complex analysis. Let us denote by Γ the unit circle {z ∈ ℂ | |z| = 1} in the complex plane ℂ. Let us consider the function

g(z) = a_{n−1}z^{n−1}. It is clear that f(z) − g(z) = z^{n} + ∑_{k=0}^{n−2} a_{k}z^{k}, and for every number z ∈ Γ

we have the inequality

|f(z) − g(z)| = |z^{n} + ∑_{k=0}^{n−2} a_{k}z^{k}| ≤ 1 + ∑_{k=0}^{n−2} |a_{k}| < |a_{n−1}| = |g(z)|.

In particular, it follows from the last formula that f(z) has no roots on the circle Γ. According to the Rouche theorem, functions f(z) and g(z) have one and the same number of roots in the disc |z| < 1. Therefore, f(z) has n − 1 roots inside the disc |z| < 1 (they are nonzero in view of the condition a_{0} ≠ 0) and one root in the exterior of this disc. According to Lemma 1, f(z) is a Pisot polynomial.

Remark 3. Obviously, Theorem 5 implies the well-known statement on the existence of Pisot polynomials of any given degree n ∈ ℕ. Note that one can say more about the set of all Pisot polynomials. Let us consider for a real number d > 0 the cube

K(d) = {(x_{1}, …, x_{n}) ∈ ℝ^{n} | |x_{i}| ≤ d , i = 1 … n} ,

and denote by Z_{n}(d) the quantity of points in ℤ^{n} ∩K(d), and let P_{n}(d) be the quantity of the points (a_{0}, a_{1}, …, a_{n−1}) ∈ ℤ^{n} ∩ K(d) such that the polynomial f(z) = z^{n} + a_{n−1}z^{n−1} + ⋯ + a_{1}z + a_{0} is a Pisot polynomial. It is not difficult to deduce from Theorem 5 the inequality

lim_{\overline{d→∞}} \frac{P_{n}(d)}{Z_{n}(d)} > 0

for every n ∈ ℕ. Let us note also that Theorem 3 implies the equality lim_{d→∞} \frac{P_{2}(d)}{Z_{2}(d)} = \frac{1}{2}.

At the end of this section we formulate two unsolved questions. For a Pisot polynomial f(z) = z^{n} + a_{n−1}z^{n−1} + ⋯ + a_{1}z + a_{0}, let us denote by M(f) the set of (n × n)-matrices with integer entries, which has f(z) as the characteristic polynomial. Thus, M(f) is the set of Pisot matrices with the common characteristic polynomial f(z).

Question 2. Let f(z) be a Pisot polynomial such that all its roots are real. Is there a symmetric matrix in the set M(f)?

Let us define the equivalence relation ∼_{GL(n,ℤ)} on the set M(f) (a definition of the group GL(n, ℤ) is given in the fifth section):

M_{1} ∼_{GL(n,ℤ)} M_{2} ⟺ ∃A ∈ GL(n, ℤ), M_{1} = AM_{2}A^{−1}

for M_{1}, M_{2} ∈ M(f). Thus M_{1} ∼_{GL(n,ℤ)} M_{2} if and only if matrices M_{1} and M_{2} are GL(n, ℤ)- similar.

Question 3. How many equivalence classes contains the quotient set M(f)/_{∼_{GL(n,ℤ)}} for a given Pisot polynomial?

3. Some properties of recurrent sequences

We shall obtain some results on recurrent sequences in this section. Besides the fact that these results have independent interest, we shall use them for a proof of the Pisot-Vijayaraghavan theorem in the next section.

Later on we shall need the simple

Lemma 3. For any polynomial f(z) = z^{n} + a_{n−1}z^{n−1} + ⋯ + a_{1}z + a_{0} with coefficients in 𝕂 (where 𝕂 is one of the fields ℂ, ℝ, ℚ or the ring of integer numbers ℤ), there is a (n × n)-matrix A with elements in 𝕂 such that its characteristic polynomial is equal to f(z).

Proof. One can take as a matrix A the matrix of the system of linear homogeneous differential equations of the first order, to which the linear differential equation y^{(n)} + a_{n−1}y^{(n−1)} + ⋯ + a_{1}y^{(1)} + a_{0}y = 0 is reduced by changing y_{1} = y, y_{2} = y^{(1)}, y_{3} = y^{(2)}, …, y_{n} = y^{(n−1)}. The same matrix will be used in the proof of Lemma 7.

Theorem 6. Let A be a square matrix with complex entries, f(z) = z^{n} + a_{n−1}z^{n−1} + ⋯ + a_{1}z + a_{0} is its characteristic polynomial, {u_{k}} is a sequence of complex numbers, satisfying the recurrent equation

u_{k+n} + a_{n−1}u_{k+n−1} + ⋯ + a_{1}u_{k+1} + a_{0}u_{k} = 0, k ∈ ℤ_{+}.

Let us suppose that f(z) has no multiple roots. Then the following statements are fulfilled. 1) There is the unique polynomial

g(z) = ∑_{l=0}^{n−1} b_{l}z^{l}, b_{l} ∈ ℂ ,

such that for all k ∈ ℤ_{+} the equation

u_{k} = tr(A^{k} · g(A)) = ∑_{m=1}^{n} g(z_{m})(z_{m})^{k},

is satisfied, where z_{m} are roots of the polynomial f(z), m = 1, …, n.

2) If all entries of the matrix A and all members of the sequence {u_{n}} belong to the field ℝ or to the field ℚ, then also all coefficients of the polynomial g(z) belong to ℝ or ℚ respectively.

3) If all entries of the matrix A belong to the field ℚ, then there are integer rational numbers (depending only on entries of the matrix A) F ≠ 0 and F_{l}^{s} (0 ≤ l ≤ n − 1, 1 ≤ s ≤ n), such that coefficients of the polynomial g(z) are expressed by formulas

b_{l} = F^{−1} · P_{l}(u_{0}, u_{1}, …, u_{n−1}), where P_{l}(y_{1}, y_{2}, …, y_{n}) = ∑_{s=1}^{n} F_{l}^{s}y_{s}.

Proof. Let us prove the first statement of the theorem. According to the Hamilton-Cayley theorem, the matrix A satisfies its characteristic equation. Thus, the equality

A^{n+k} + ∑_{m=0}^{n−1} a_{m}A^{m+k} = 0.

is fulfilled. By multiplying both sides of the last equation on the right by arbitrary matrix C and calculating the trace of both sides, we obtain that the sequence {v_{k}}, where v_{k} = tr(A^{k} · C), satisfies recurrent equation

v_{k+n} + a_{n−1}v_{k+n−1} + ⋯ + a_{1}v_{k+1} + a_{0}v_{k} = 0, k ∈ ℤ_{+}.

Now we shall indicate a matrix C such that {v_{k}} = {u_{k}}. We shall seek it in the form

C = ∑_{l=0}^{n−1} b_{l}A^{l}, where b_{l} are some complex numbers. To prove the coincidence of the sequences

{v_{k}} and {u_{k}}, it is enough to establish the coincidence of their first n members. I.e., the following equalities

u_{m} = ∑_{l=0}^{n−1} b_{l} · tr(A^{m+l}), m ∈ {0, …, n − 1}

must be satisfied. One can write these equalities in the form of a system of linear equations

( \begin{matrix}tr A^{0} & tr A^{1} & ⋯ & tr A^{n−1} \\ tr A^{1} & tr A^{2} & ⋯ & tr A^{n} \\ ⋯ & ⋯ & ⋯ & ⋯ \\ tr A^{n−1} & tr A^{n} & ⋯ & tr A^{2n−2} \end{matrix} ) ( \begin{matrix}b_{0} \\ b_{1} \\ ⋯ \\ b_{n−1} \end{matrix} ) = ( \begin{matrix}u_{0} \\ u_{1} \\ ⋯ \\ u_{n−1} \end{matrix} ) .  (19)

Remark now that the matrix of this system of equations has the form V · V^{t}, where

V = ( \begin{matrix}1 & 1 & ⋯ & 1 \\ z_{1} & z_{2} & ⋯ & z_{n} \\ ⋯ & ⋯ & ⋯ & ⋯ \\ z_{1}^{n−1} & z_{2}^{n−1} & ⋯ & z_{n}^{n−1} \end{matrix} ) ,

while z_{i} are roots of the polynomial f(z). Thus, V is a Vandermonde matrix with the determinant ∏_{i<j}(z_{j} − z_{i}) ≠ 0. It means that the determinant of the matrix equation (19)

is equal to D = ∏_{i<j}(z_{j} − z_{i})^{2} ≠ 0, therefore, the system (19) is solvable relatively to the

variables b_{i}. Let us note also that the number D is the discriminant of the polynomial f(z).

Since for roots of the polynomial f(z) (z_{m}, m = 1, …, n) the equality tr A^{k} = ∑_{m=1}^{n}(z_{m})^{k}

(k ∈ ℤ_{+}) is fulfilled, we get that

u_{k} = tr (A^{k} · ∑_{l=0}^{n−1} b_{l}A^{l}) = ∑_{l=0}^{n−1} b_{l} tr A^{k+l} = ∑_{l=0}^{n−1} b_{l} ∑_{m=1}^{n}(z_{m})^{k+l} =

= ∑_{m=1}^{n} (∑_{l=0}^{n−1} b_{l}(z_{m})^{l}) · (z_{m})^{k} = ∑_{m=1}^{n} g(z_{m})(z_{m})^{k}.

Consequently, we proved the existence of the required b_{i}; the uniqueness of the polynomial g(z) follows from the fact that the system (19) has the unique solution.

The second statement of the theorem is practically evident. One needs only to remark that in the case when all entries of the matrix A and all u_{k} are real or rational, the obtained coefficients b_{i} of the polynomial g(z) will be also real or rational.

The third statement of the theorem follows immediately from Cramer’s rule for a solution of systems of linear equations.

Lemma 4. Let f(z) = z^{n} + a_{n−1}z^{n−1} + ⋯ + a_{1}z + a_{0} be a polynomial with rational coefficients, which is irreducible over ℚ, while {u_{k}} is a nonzero sequence of rational numbers, satisfying the recurrent equation

u_{k+n} + a_{n−1}u_{k+n−1} + ⋯ + a_{1}u_{k+1} + a_{0}u_{k} = 0, k ∈ ℤ_{+}.

Then there are complex numbers C_{m} ≠ 0 (1 ≤ m ≤ n) such that for all k ∈ ℤ_{+} the equality

u_{k} = ∑_{m=1}^{n} C_{m}(z_{m})^{k}

is satisfied, where z_{i} are roots of the polynomial f(z). Moreover, C_{m} ∈ ℚ(z_{m}).

Proof. According to Lemma 3, there is a square matrix A with rational entries, which has the characteristic polynomial f(z). By Theorem 6, there is a polynomial

g(z) = ∑_{l=0}^{n−1} b_{l}z^{l}, b_{l} ∈ ℚ ,

such that for all k ∈ ℤ_{+} the equality

u_{k} = tr(A^{k} · g(A)) = ∑_{m=1}^{n} g(z_{m})(z_{m})^{k},

is fulfilled, where z_{m}, m = 1, …, n are roots of the polynomial f(z). Thus, one can take g(z_{m}) as C_{m}. It remains to show that for every m ∈ {1, …, n}, the inequality C_{m} ≠ 0 is fulfilled. But if g(z_{m}) = 0 for some number, then this contradicts to irreducibility of the polynomial f(z). Really, g(z) is the polynomial with rational coefficients and its degree is less than the degree of the polynomial f(z). Therefore, the existence of a common root of these polynomials implies the reducibility of f(z) over the field ℚ. Finally, since C_{m} = g(z_{m}), then C_{m} ∈ ℚ(z_{m}).

Lemma 5. Let suppose that a sequence of complex numbers {v_{k}} satisfies the equation

v_{k} = ∑_{l=1}^{m} C_{l}(z_{l})^{k},

where C_{l} ∈ ℂ, z_{l} are mutually distinct complex numbers and |z_{l}| ≥ 1 for all l = 1, …, m. Hence, if v_{k} → 0 when k → ∞, then C_{l} = 0 for all l.

Proof. At first we shall prove the lemma under additional condition that absolute values of all numbers z_{l} are equal to 1. Let us consider for this goal the discrete dynamical system on the torus 𝕋 = (𝕊^{1})^{m} (𝕊^{1} = ℝ/(2πℤ),) supplied with invariant probability Lebesgue measure. This system is defined by the map A : 𝕋 → 𝕋,

A(φ_{1}, ..., φ_{m}) = (φ_{1} + α_{1}, ..., φ_{m} + α_{m}),

where α_{l} = Arg(z_{l}). The map A preserves volumes. Let us consider function F : 𝕋 → ℂ, defined by formula

F (φ) = ∑_{i=1}^{m} C_{l}e^{φ_{l}\sqrt{−1}}.

Suppose, that 𝕆 = (0, …, 0). By the condition of the lemma, F (A^{k}(𝕆)) → 0 when k → ∞. If for some m the inequality |F (A^{m}(𝕆))| > ϵ > 0 is satisfied, then the same inequality is satisfied for all points x in some neighborhood U of the point A^{m}(𝕆) on the torus 𝕋. By the Poincare recurrence theorem, members of the sequence A^{k}(𝕆) get into the neighborhood U infinitely many times. Thus, the condition F (A^{k}(𝕆)) → 0 is not satisfied when k → ∞. It follows from the obtained contradiction that for every natural number m, the equality F (A^{m}(𝕆)) = 0 is fulfilled. Further, it is enough to note that the matrix of the homogeneous

system of linear equations ∑_{l=1}^{m} C_{l}(z_{l})^{k} = 0, k = 0, …, n−1, is a nondegenerate Vandermonde

matrix, and therefore, all the numbers C_{l} must be equal to zero.

Let us prove now the lemma in general case. Suppose that the lemma is not true. Then for some sequence of complex numbers {v_{k}} such that v_{k} → 0 when k → ∞, for some mutually distinct z_{l} (|z_{l}| ≥ 1) and for some complex numbers C_{l} ≠ 0, l = 1, …, m, we

have the equality v_{k} = ∑_{l=1}^{m} C_{l}(z_{l})^{k}. Let us order z_{l} by decreasing of their absolute values

|z_{l}| and let us use the notation t = |z_{1}|. Let s (1 ≤ s ≤ m) be such that |z_{l}| = t > 1 when l = 1, …, s, while |z_{l}| < t when l > s. Consider the sequence {ṽ_{k}}, defined by the equation

ṽ_{k} = \frac{v_{k}}{t^{k}} − ∑_{l=s+1}^{m} C_{l} (\frac{z_{l}}{t} )^{k} .

Obviously, ṽ_{k} → 0 when k → ∞. Furthermore,

ṽ_{k} = ∑_{l=1}^{s} C_{l}(z̃_{l})^{l},

where z̃_{l} = z_{l}/t, |z̃_{l}| = 1 if l = 0, …, s. But according to the first part of the proof, we get that C_{l} = 0 when 1 ≤ l ≤ s, which contradicts our hypothesis. Thus the lemma is completely proved.

Lemma 6 ([14], Chapter VIII, §2, Lemma 3). Let us suppose that there is a number γ ≠ 0 in the field ℚ(λ) of an algebraic number λ (of degree r) such that all the numbers γ, γλ, γλ^{2}, … are equal to polynomials of degree r − 1 with integer rational coefficients relatively to λ. Then λ is an integer algebraic number.

Theorem 7. Let {u_{k}} be an integer nonzero sequence, which satisfies the recurrent equation

u_{k+n} + a_{n−1}u_{k+n−1} + ⋯ + a_{1}u_{k+1} + a_{0}u_{k} = 0, k ∈ ℤ_{+},

where a_{l} ∈ ℚ, l = 0, …, n − 1, and the polynomial

f(z) = z^{n} + a_{n−1}z^{n−1} + ⋯ + a_{1}z + a_{0}

is irreducible over ℚ. Then all the numbers a_{l}, 0 ≤ l ≤ n − 1, are integer rational numbers.

Proof. Since any irreducible polynomial has no multiple roots, then according to Lemma 6, we have the equality

u_{k} = ∑_{m=1}^{n} g(z_{m})(z_{m})^{k}, k ∈ ℤ_{+}  (20)

for some polynomial g(z) with rational coefficients. Let us consider a natural number p and the sequence {ũ_{k}} such that ũ_{k} = u_{k+p} for k ∈ ℤ_{+}. It is clear that such sequence also satisfies the recurrent equation

ũ_{k+n} + a_{n−1}ũ_{k+n−1} + ⋯ + a_{1}ũ_{k+1} + a_{0}ũ_{k} = 0, k ∈ ℤ_{+}.

By the statement 3) of Theorem 6,

ũ_{k} = ∑_{m=1}^{n} g̃(z_{m})(z_{m})^{k}, k ∈ ℤ_{+},

for some polynomial

g̃(z) = ∑_{l=0}^{n−1} b_{l}z^{l} ,

and there are integer rational numbers F ≠ 0 and F_{l}^{s} (0 ≤ l ≤ n − 1, 1 ≤ s ≤ n) such that coefficients of the polynomial g̃(z) are expressed by formulas

b_{l} = F^{−1} · P_{l}(u_{p}, u_{p+1}, …, u_{n+p−1}), where P_{l}(y_{1}, y_{2}, …, y_{n}) = ∑_{s=1}^{n} F_{l}^{s}y_{s}.

Let us examine numbers A_{l} = P_{l}(u_{p}, u_{p+1}, …, u_{n+p−1}). Evidently, they are integer rational numbers. Therefore, we have the equality

F · ũ_{k} = ∑_{m=1}^{n} (∑_{l=0}^{n−1} A_{l}(z_{m})^{l}) (z_{m})^{k}, k ∈ ℤ_{+}  (21)

Since ũ_{k} = u_{k+p}, then we obtain from the equalities (20) and (21) that

F · ũ_{k} − F · u_{k+p} = ∑_{m=1}^{n} C̃_{m}(z_{m})^{k} = 0, k ∈ ℤ_{+},  (22)

where C̃_{m} = ∑_{l=0}^{n−1} A_{l}(z_{m})^{l} − F · g(z_{m})(z_{m})^{p}. It is not difficult to understand that C̃_{m} = 0 for

all 1 ≤ m ≤ n. Indeed, if we consider the system of equations (22) relatively to variables C̃_{m} where 0 ≤ k ≤ n − 1, then the matrix of this system is a nondegenerate Vandermonde matrix. If λ is any root z_{m} of the polynomial f(z), we get the equality

F · g(λ) · λ^{p} = ∑_{l=0}^{n−1} A_{l}λ^{l}.

It follows from this equality and Lemma 6 that λ is an integer algebraic number. In fact, the number p ∈ ℕ has been taken arbitrarily, γ = F · g(λ) ∈ ℚ(λ) and g(λ) ≠ 0, as it follows from the proof of Lemma 4. Further, since λ is a root of the polynomial f(z), which is irreducible over the field of rational numbers, it means that all coefficients of the last polynomial must be integer rational numbers.

Remark 4. The irreducibility condition for the polynomial f(z) in the statement of Theorem 7 is essential. In order to illustrate this, let us consider the sequence {u_{n} = 2^{n}}. For every rational number p ≠ 0 this sequence satisfies the recurrent equation

u_{k+2} − \frac{2p + 1}{p}u_{k+1} + \frac{2}{p}u_{k} = 0, k ∈ ℤ_{+},

We have such effect, because the polynomial

z^{2} − \frac{2p + 1}{p}z + \frac{2}{p} = (z − \frac{1}{p}) (z − 2)

is reducible.

4. Proof of the Pisot-Vijayaraghavan theorem

A classical proof of the Pisot-Vijayaraghavan theorem is given, for example, in the book [14]. We consider as possible to give another proof in this paper, which in our view describes better interconnections of Pisot numbers theory with other branches of Mathematics such as the theory of recurrent sequences and the theory of dynamical systems. We shall get the proof on the ground of properties of recurrent sequences from the previous section.

Let us consider a number λ, being a root of a polynomial

f(z) = z^{n} + a_{n−1}z^{n−1} + ⋯ + a_{1}z + a_{0}

with rational coefficients, irreducible over ℚ. For θ ∈ ℚ(λ), let us indicate an effective way to calculate the algebraic trace Tr(θλ^{p}). We have the following Lemma 7. Let us consider the equation θ = h(λ) = ∑_{l=0}^{n−1} c_{l}λ^{l} with rational coefficients c_{l}.

Then the following statements are fulfilled.

1) For any p ∈ ℤ_{+}, the equality

Tr(θλ^{p}) = ∑_{m=1}^{n} h(z_{m})(z_{m})^{p},

is satisfied, where z_{m} are roots of the polynomial f(z), m = 1, …, n.

2) Moreover, if λ is an integer algebraic number, then all the numbers Tr(θλ^{p}) are rational with denominators not greater than the least common multiple of the denominators of the coefficients c_{l}, l = 0, …, n − 1.

Proof. Let us prove the first statement of the lemma. Let us choose a basis {ξ_{l}}_{l=1}^{n} in ℚ(λ) such that ξ_{l} = λ^{l−1}. Consider the matrix

M = ( \begin{matrix}0 & 1 & 0 & ⋯ & 0 \\ 0 & 0 & 1 & ⋯ & 0 \\ ⋯ & ⋯ & ⋯ & ⋯ & ⋯ \\ 0 & 0 & 0 & ⋯ & 1 \\ −a_{0} & −a_{1} & −a_{2} & ⋯ & −a_{n−1} \end{matrix} ) ,

of the linear map

L : ℚ(λ) → ℚ(λ), L(y) = y · λ

in the chosen basis {ξ_{l}}_{l=1}^{n} ([7], Chapter VI, §47). It is clear that Tr(λ) = tr(M). One can

easily see that Tr(λ^{q}) = tr(M^{q}) = ∑_{m=1}^{n}(z_{m})^{q} for q ∈ ℤ_{+}. Therefore,

Tr(θλ^{p}) = Tr (λ^{p} · ∑_{l=0}^{n−1} c_{l}λ^{l}) = ∑_{l=0}^{n−1} c_{l} Tr λ^{p+l} = ∑_{l=0}^{n−1} c_{l} tr M^{p+l} =

= ∑_{l=0}^{n−1} c_{l} ∑_{m=1}^{n}(z_{m})^{p+l} = ∑_{m=1}^{n} (∑_{l=0}^{n−1} c_{l}(z_{m})^{l}) · (z_{m})^{p} = ∑_{m=1}^{n} h(z_{m})(z_{m})^{p}.

Let us prove now the second statement of the lemma. Since λ is an integer algebraic number, then all coefficients of the polynomial f(z) and all entries of the matrix M are integer rational numbers. Now it is enough to refer to the equality

Tr(θλ^{p}) = ∑_{l=0}^{n−1} c_{l} tr M^{p+l}.

Proof of the Pisot-Vijayaraghavan theorem. At first we shall show that for any Pisot number λ > 1 we have P_{λ} ≠ {0}. Let us verify, for example, that 1 ∈ P_{λ}. According to the statement 2) of Lemma 7, we get that Tr(λ^{p}) ∈ ℤ for all p ∈ ℤ_{+}. On the other hand, according to the statement 1) of lemma 7, we have the equality

Tr(λ^{p}) = ∑_{m=1}^{n}(z_{m})^{p}

for all p ∈ ℤ_{+}, where λ = z_{1}, z_{2}, …, z_{m} are roots of the polynomial f(z). According to the definition of Pisot number, |z_{m}| < 1 for m ≥ 2. Therefore, λ^{p} − Tr(λ^{p}) = o(1) when p → ∞. Since Tr(λ^{p}) ∈ ℤ, we get that 1 ∈ P_{λ}.

Now let λ > 1 be an algebraic number of degree n, i.e. there is a polynomial

f(z) = a_{n}z^{n} + a_{n−1}z^{n−1} + ⋯ + a_{1}z + a_{0}, a_{n} > 0,

with integer coefficients, which is irreducible over rational numbers and has λ as one of its roots; and P_{λ} ≠ {0}. Consequently, there is a ∈ ℝ such that a ≠ 0 and

∥aλ^{n}∥ → 0 when n → ∞.  (23)

We shall show that λ is a Pisot number and a ∈ ℚ(λ). We obtain from the equality (23) that

aλ^{k} = u_{k} + o(1) when k → ∞

for some integer sequence {u_{k}}. Evidently, this sequence is nonzero and for 0 ≤ i ≤ n the equalities

a · a_{i}λ^{k+i} = a_{i}u_{k+i} + o(1) when k → ∞,

are fulfilled, by summing of which we get

0 = aλ^{k} (∑_{i=0}^{n} a_{i}λ^{i}) = ∑_{i=0}^{n} a_{i}u_{k+i} + o(1) when k → ∞.

Consequently, it is necessary that for sufficiently large indices k the equality

∑_{i=0}^{n} a_{i}u_{k+i} = 0

is satisfied. According to Theorem 7, it must be a_{n} = 1. Since the polynomial f(z) is irreducible, then according to Lemma 4, for sufficiently large k, we have the expansion

u_{k} = ∑_{i=1}^{n} C_{i}(z_{i})^{k}

for appropriate (maybe, complex) numbers C_{i} ≠ 0, where λ = z_{1}, z_{2}, …, z_{n} are roots of the polynomial f(z). Since

aλ^{k} = ∑_{i=1}^{n} C_{i}(z_{i})^{k} + o(1) when k → ∞,

then, if for some i ≥ 2 inequality |z_{i}| ≥ 1 is satisfied, then, according to Lemma 5, we have C_{i} = 0, which contradicts to Lemma 4. Therefore, the inequality |z_{i}| < 1 is satisfied for all i ≥ 2. Thus, the polynomial f(z) is a Pisot polynomial, while λ is a Pisot number. Moreover, it is clear that a = C_{1}. Applying Lemma 4 again, we get that a ∈ ℚ(λ).

Now let us give the complete characterization of the set P_{λ} for the Pisot number λ. As we have showed above, P_{λ} ⊂ ℚ(λ). Let us consider now an arbitrary a ∈ P_{λ} ⊂ ℚ(λ). Then

there is a polynomial h(z) = ∑_{l=0}^{n−1} c_{l}z^{l} with coefficients in ℚ such that a = h(λ). According

to Lemma 7, for any p ∈ ℤ_{+} we have the equality

Tr(aλ^{p}) = ∑_{m=1}^{n} h(z_{m})(z_{m})^{p},

where z_{m} are roots of the polynomial f(z), m = 1, …, n, z_{1} = λ. Since |z_{m}| < 1 for m ≥ 2 and h(λ) = a, then

Tr(aλ^{p}) = aλ^{p} + o(1) when p → ∞.

Since ∥aλ^{p}∥ → 0 when p → ∞, then, according to the statement 2) of Lemma 7, we get that Tr(aλ^{p}) ∈ ℤ for sufficiently large p.

Conversely, if Tr(aλ^{p}) ∈ ℤ for sufficiently large p, then ∥aλ^{p}∥ → 0 when p → ∞, because

aλ^{p} = Tr(aλ^{p}) + o(1) when p → ∞.

Thus, for the Pisot number λ we get

P_{λ} = {a ∈ ℚ(λ) | Tr(aλ^{n}) ∈ ℤ for sufficiently large n}.

Remark 5. It follows immediately from the statement 2) of Lemma 7 and the Pisot-Vijaya-raghavan theorem that for any Pisot number λ, a number θ, satisfying the equality θ =

∑_{l=0}^{n−1} c_{l}λ^{l} for some integer rational numbers c_{l} (l = 0, …, n − 1), belongs to the set P_{λ}.

5. General information on the group GL(2, ℤ) and some of its subsemigroups

The group GL(n, ℤ) of all invertible integer (n × n)-matrices is naturally identified with the group of all invertible linear maps of n-dimensional (real) vector space, preserving a fixed lattice of this space. It consists of integer (n × n)-matrices of determinant ±1. Therefore, some authors (see, for example, [16]) call it the unimodular group. Equally often by the unimodular group one means its subgroup SL(n, ℤ) of index 2, consisting of matrices of determinant 1. The group GL(n, ℤ) (and its subgroup SL(n, ℤ) in the case of even n) has the center C of order 2, generated by the central inversion, inverting the sign of each coordinate. Its quotient group P GL(n, ℤ) := GL(n, ℤ)/C is the projective (unimodular) group. If n is odd, then the pairs of groups P GL(n, ℤ) and SL(n, ℤ), GL(n, ℤ) and SL(n, ℤ) × C are naturally isomorphic; for even n, the quotient group P GL(n, ℤ) contains the subgroup P SL(n, ℤ) := SL(n, ℤ)/C of index 2. The last group in the case n = 2 is isomorphic to the (discrete) (so-called modular) group Γ of linear-fractional transformations

z′ = \frac{az + b}{cz + d}  (24)

of the upper complex half-plane (serving as the Poincare model of the Lobachevskii plane) with integer coefficients, satisfying the condition ac − bd = 1.

We shall denote by f(A) the linear-fractional transformation (24) of the whole complex plane ℂ, corresponding to the matrix

A = (\begin{matrix}a & b \\ c & d \end{matrix})

in GL(2, ℤ). For n ≥ 2, the group GL(n, ℤ) is generated by three matrices for odd n and by two matrices for even n, [16]. Let us write generators and relations for n = 2. The group GL(2, ℤ) has genetic code (see [16])

\{R_{1} = (\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix}) , R_{2} = (\begin{matrix}−1 & 0 \\ 1 & 1 \end{matrix}) , R_{3} = (\begin{matrix}−1 & 0 \\ 0 & 1 \end{matrix});

R_{1}^{2} = R_{2}^{2} = R_{3}^{2} = E, (R_{1}R_{2})^{2} = (R_{1}R_{3})^{2} = Z, Z^{2} = E}.

The group SL(2, ℤ) has genetic code

\{S := R_{1}R_{2} = (\begin{matrix}1 & 1 \\ −1 & 0 \end{matrix}) , T := R_{1}R_{3} = (\begin{matrix}0 & 1 \\ −1 & 0 \end{matrix});

S^{3} = T^{2} = Z = (\begin{matrix}−1 & 0 \\ 0 & −1 \end{matrix}) , Z^{2} = E\}.

The modular group Γ has genetic code

{σ, τ; σ^{3} = τ^{2} = 1}

and it is a free product of two cyclic groups of orders 3 and 2.

As generators of the group GL(2, ℤ) one can take matrices

u := R_{1}, v := R_{1}R_{3}R_{2}R_{1} = (\begin{matrix}1 & 1 \\ 0 & 1 \end{matrix}) .

Then

R_{2} = v^{−1}uv, R_{3} = uvuv^{−1}uv.

Theorem 8. The subsemigroup GL_{+}(2, ℤ) of the group GL(2, ℤ), consisting of matrices with nonnegative entries, has genetic code

{u, v; u^{2} = E.}

Proof. At first let us prove that the semigroup, generated by elements u, v, coincides with GL_{+}(2, ℤ). Evidently, u, v ∈ GL_{+}(2, ℤ). Rearranging rows and (or) columns of any matrix A in GL_{+}(2, ℤ), i.e. multiplying, if it’s necessary, the matrix A by the matrix u on the left and (or) on the right, one can achieve that the maximal entry of the obtained matrix Z will be z_{22} > 0. Moreover, if z_{22} = z_{12} (or z_{22} = z_{21}) then, rearranging, if it’s necessary, rows and columns, one can assume that z_{11} ≤ z_{21} (respectively z_{11} ≤ z_{12}), i.e. Z is non-decreasing by columns and rows. Otherwise, if the condition of non-decreasing for Z by rows and columns be violated, one can easily verify that Z = E. If Z = E, then A = E or A = u. If Z is non-decreasing by columns and rows, then by Theorem 1 the matrix Z is uniquely represented in the form of the product (10). In turn, every factor of this product, corresponding to the natural number q_{i}, i = 1, ..., n + 1, is the matrix uv^{q_{i}}.

The uniqueness of a representation of the matrix A in the form of the product of powers of elements u, v with nonnegative exponents, where exponents of powers for element u do not exceed 1, follows from the above arguments and Theorem 1.

It follows from Theorems 8 and 1 the following

Corollary 1. The set of integer (2×2)-matrices with nonnegative entries, non-decreasing by rows and columns, or, which is the same, of matrices of the form (10), constitutes the free (non-commutative) subsemigroup GL_{+,≤}(2, ℤ) of the semigroup GL_{+}(2, ℤ) with countable set of generators of the form uv^{n}, n ∈ ℕ, which does not admit a finite generating set.

Analogously, the set of all matrices in GL_{+}(2, ℤ), non-decreasing by rows and columns, constitutes the free (non-commutative) semigroup GL_{+,≥}(2, ℤ) with a countable set of generators of the form v^{n}u, n ∈ ℕ, which does not admit a finite generating set.

The subsemigroup SGL_{+}(2, ℤ) − E of the semigroup GL_{+}(2, ℤ), consisting of matrices of determinant 1 and different from the unit matrix, is a free semigroup with the generators v and uvu.

On the ground of Theorem 8 and Corollary 1 we get successively all the statements of Corollary 2.

Corollary 2. For any element A of semigroup GL_{+}(2, ℤ), it is satisfied exactly one alternative:

1) A = E;

2) A = u;

3) A = v^{n}, n ∈ ℕ;

4) A ∈ GL_{+,≤}(2, ℤ);

5) A ∈ GL_{+,≥}(2, ℤ);

6) A ∈ GL_{+,≤}(2, ℤ)u;

7) A ∈ GL_{+,≥}(2, ℤ)v^{n}, n ∈ ℤ.

Furthermore, every set G_{i}, consisting of matrices A with the property i), besides G_{2}, is a subsemigroup in GL_{+}(2, ℤ), while the set G_{1,2} := G_{1} ∪ G_{2} is a two-element group. Thus, the semigroup GL_{+}(2, ℤ) is an union of six mutually disjoint subsemigroups G_{1,2} and G_{k}, where k = 3, …, 7; moreover, only G_{3}, G_{4}, G_{5} are free semigroups.

The conjugation of the group GL(2, ℤ) by the element u is an involutive automorphism φ. The automorphism φ translates semigroups GL_{+}(2, ℤ), G_{1,2} to themselves, interchanges semigroups G_{4},G_{5}, and maps semigroups G_{3} and G_{7} onto some semigroups φ(G_{3}) and φ(G_{7}), composing a partition of the semigroup G_{6}; φ maps subsemigroups φ(G_{3}) and φ(G_{7}) of the semigroup G_{6} onto semigroups G_{3} and G_{7}.

Thus, the semigroup GL_{+}(2, ℤ) splits into seven mutually disjoint semigroups G_{1,2}; G_{3}, φ(G_{3}); G_{5}, G_{4}; G_{7}, φ(G_{7}), where pairs of semigroups, separated by the comma, are pairwise isomorphic by means of the automorphism φ and the union of all first (respectively, second) semigroups of these pairs also constitute some semigroup G_{odd} (G_{even} = G_{4} ∪ G_{6}). The semigroup GL_{+}(2, ℤ) − G_{1,2} splits into subsemigroups G_{odd} and G_{even}, pairwise isomorphic by means of φ. Sets G_{3} ∪ G_{7}, G_{5} ∪ G_{7}, G_{4} ∪ G_{7}, G_{5} ∪ G_{6} and their images under the automorphism φ are semigroups.

The antiautomorphism φ_{−} of the group GL(2, ℤ), changing the order of letters in the alphabet {u, v} to the opposite, commutes with φ, acts identically on G_{1,2}, G_{3} and φ(G_{3}), maps semigroups φ(G_{7}) and G_{7} onto themselves, and also interchanges semigroups G_{5} and G_{4}.

Let GL^{+}(2, ℤ) be a subsemigroup of the group GL(2, ℤ), consisting of matrices with positive entries. On the ground of Corollary 2 we get

Corollary 3. The semigroups GL^{+}(2, ℤ) is a two-sided ideal of the semigroup GL_{+}(2, ℤ), containing in the union of (disjoint) semigroups G_{4}, G_{5}, G_{6}, G_{7}; moreover,

\begin{aligned}G_{4}^{+} & := & GL^{+}(2, ℤ) ∩ G_{4} & = & G_{4}G_{4}, \\ G_{5}^{+} & := & GL^{+}(2, ℤ) ∩ G_{5} & = & G_{5}G_{5}, \\ G_{6}^{+} & := & GL^{+}(2, ℤ) ∩ G_{6} & = & φ(G_{7}), \\ G_{7}^{+} & := & GL^{+}(2, ℤ) ∩ G_{7} & = & G_{7}. \end{aligned}

All these intersections, as well as GL^{+}(2, ℤ), are non-free. The automorphism φ from Corollary 2 interchanges pairs of (isomorphic) semigroups G_{4}^{+},G_{5}^{+} and G_{6}^{+},G_{7}^{+}. The subsemigroup G_{4}^{+} of the free semigroup G_{4} has the unique smallest countable generating set, consisting of matrices, which are indecomposable into a product in G_{4}^{+}, and admits a countable (but does not admit a finite) set of defining relations with the genetic code (see (8))

{M(p, q), M(r, s, t), p, q, r, s, t ∈ ℕ; M(p, q)M(r, s, t) = M(t, p, q)M(r, s),
M(r, s, t)M(r_{1}, s_{1}, t_{1}) = M(s, t)M(t_{1}, r)M(r_{1}, s_{1})}.

The subsemigroup SGL_{+,≤}(2, ℤ) of the semigroup GL_{+,≤}(2, ℤ), consisting of matrices of determinant 1, is contained in G_{4}^{+} and has a system of the free generators {M(p, q); p, q ∈ ℕ}.

At the end of the section, we give the statement on a connection between semigroups of the group GL(2, ℤ), investigated above, and Pisot numbers.

Proposition 1. Each element of one of the semigroup GL_{+,≤}(2, ℤ), GL_{+,≥}(2, ℤ) or GL^{+}(2, ℤ) is a Pisot matrix.

Proof. Let Z = (z_{ij}) (i, j = 1, 2) be any matrix of one of the above semigroup, and let

λ^{2} + pλ + q = 0  (25)

be its characteristic equation. Then q = ±1. According to Theorem 3, it is enough to prove the inequality |p| > |1 + q|. If q = −1, then the condition |p|(= z_{11} + z_{22}) > |1 + q| = 0 is evidently satisfied. Let suppose that q = 1. Then |1 + q| = 2. In the case Z ∈ GL^{+}(2, ℤ), equalities z_{11} = z_{22} = 1 are impossible; therefore |p| = z_{11}+z_{22} > 2. When Z ∈ GL_{+,≤}(2, ℤ), it is possible only the case z_{11} ≥ 1; then z_{22} ≥ 2 and |p| > 2. The statement is also fulfilled in the case Z ∈ GL_{+,≥}(2, ℤ), because the symmetry relatively to the secondary diagonal translates a matrix in GL_{+,≥}(2, ℤ) to a matrix in GL_{+,≤}(2, ℤ), and does not change p, q.

6. Asymptotic properties of linear-fractional transformations

Let us consider the question: when an infinite sequence of linear-fractional transformations z_{n} := f(M(q_{1}, …, q_{n}))(z) (see (8) and (24)) of a point z ∈ ℂ, corresponding to a selected sequence of natural numbers {q_{n}}, converges to a point in ℂ (in usual topology) and what are possible limits of the sequences z_{n}? The main role in the further reasoning play numbers

μ(q) = [q; q, q, …] = q + \frac{1}{q + \frac{1}{q + ...}} .  (26)

The number μ := μ(1) is known as the golden section. Therefore it is appropriate to call the number μ(q) by a generalized golden section. The answer to the above question gives the following

Theorem 9. For any point z ∈ ℂ, z ≠ −(1/[0; q_{1}, q_{2}, …]), the sequence of points {z_{n} = f(M(q_{1}, …, q_{n}))(z)} is convergent if and only if the sequence {q_{n}} converges to infinity or stabilizes. In both two cases lim_{n→∞} z_{n} does not depend on a choice of the point z, is equal to zero in the first case and to infinite (periodic) continued fraction

\frac{1}{μ(q)} = [0; q, q, …]

in the second case, if the sequence {q_{n}} stabilizes on the number q ∈ ℕ .

Proof. On the ground of formulas (10) and (24), we have

z_{n} = f(M(q_{1}, …, q_{n+1}))(z) = \frac{P_{n}z + Q_{n}}{P_{n+1}z + Q_{n+1}} = \frac{Q_{n}}{Q_{n+1}} \frac{\frac{P_{n}}{Q_{n}} z + 1}{\frac{P_{n+1}}{Q_{n+1}} z + 1}.

As a consequence of (2),(3), this sequence has a limit when n → ∞ for any z ≠ −(1/[0; q_{1}, q_{2}, …]) if and only if there is a limit of the sequence (Q_{n}/Q_{n+1}); moreover, these limits coincide.

The formula (14) gives the value of the fraction a_{n+1} := (Q_{n}/Q_{n+1}). It is known (see [21]), that for n ≥ 3, inequalities

[0; q_{n+1}, q_{n}] < a_{n+1} < [0; q_{n+1}]  (27)

are satisfied. It follows from here that there are zero limits of sequences a_{n}, z_{n}, if the sequence q_{n} tends to +∞.

If the sequence q_{n} is bounded from above by a number q and does not stabilize when n → ∞, then for every natural number k there are natural numbers m = n + 1 > n > k, such that q_{m} < q_{n} ≤ q. Then, on the ground of (27), we get inequalities

a_{n} < [0; q_{n}] ≤ [0; q_{n+1} + 1] < [0; q_{n+1}, q_{n+1} + 1]
≤ [0; q_{n+1}, q_{n}] < a_{n+1} = a_{m}.

Consequently,

|a_{m} − a_{n}| > [0; q_{m}, q_{m} + 1] − [0; q_{m} + 1] =

\frac{q_{m}}{(q_{m} + 1)(q_{m}(q_{m} + 1) + 1)} ≥ \frac{1}{(q + 1)(q(q + 1) + 1)}

and the sequence a_{n} can not converge.

If q_{n} is not bounded from above and does not tend to +∞, then there is a number q > 0 with the property that for every natural k there are natural numbers n, m > k, such that q_{n} ≤ q < q + 1 < q_{m}. Then in view of (27),

a_{m} < [0; q_{m}] < [0; q_{n} + 1] ≤ [0; q_{n}, q_{n−1}] < a_{n},

|a_{n} − a_{m}| > [0; q_{n} + 1] − [0; q_{m}] > \frac{1}{q + 1} − \frac{1}{q + 2} = \frac{1}{(q + 1)(q + 2)}.

Therefore, the sequence a_{n} can not converge.

It remains the case, when the sequence q_{n} stabilizes, say, on q, beginning with a index k. Then for every number n > k we get

|a_{n} − [0; q, q, …]| ≤ |a_{n} − [0; q_{n}, …, q_{k}]| + |[0; q_{n}, …, q_{k}] − [0; q, q, …]|.

Under this [0; q_{n}, …, q_{k}] is simultaneously the (n − k)-th convergent fraction P_{n−k}/Q_{n−k} both for a_{n} and for [0; q, q, …]. It follows from formulas (13) and (4) that every positive summand in the right part of the last inequality is less than the number 1/(Q_{n−k})^{2}. Consequently, there is

lim_{n→∞} z_{n} = lim_{n→∞} a_{n} = [0; q, q, …],

which completes the proof.

Remark 6. In addition to Theorem 9, let us remark that in the case, when q_{i} ≡ q, we have z_{n} ≡ z, if z = −\frac{1}{[0;q_{1},q_{2},...]} = −[q; q, q, …] = −μ(q) (or z = \frac{1}{μ(q)}), because f(M(q))(z) = z for these z. Restrictions of transformations f(M(q)^{2n}) to the Lobachevskii plane (that is the upper complex half-plane) constitute the semigroup of hyperbolic motions of the plane with fixed points −μ(q) and \frac{1}{μ(q)} on the ideal boundary of the plane.

7. Relations between elements of natural powers of (2 × 2)-matrices

Now we turn to the description problem for interrelation between coefficients of matrices of the form Z^{n}.

Theorem 10. Let us suppose that a (2 × 2)-matrix Z = (z_{ij}) has distinct (maybe, complex) nonzero eigenvalues, and z_{12} ≠ 0. Then entries of the matrix

Z^{n+1} = (\begin{matrix}P_{n} & Q_{n} \\ R_{n} & T_{n} \end{matrix})

satisfy relations

Q_{n} = \frac{z_{12}(λ^{n+1} − η^{n+1})}{λ − η}, R_{n} = \frac{z_{21}}{z_{12}} Q_{n},  (28)
T_{n} − P_{n} = \frac{z_{22} − z_{11}}{z_{12}} Q_{n}, T_{n} + P_{n} = λ^{n+1} + η^{n+1},  (29)

where λ and η are distinct roots of the characteristic equation of the matrix Z.

Proof. Let us consider matrices

C := (\begin{matrix}\frac{1}{λ−η} & z_{12} \\ \frac{η−z_{11}}{z_{12}(λ−η)} & λ − z_{11} \end{matrix}) , B := (\begin{matrix}λ − z_{11} & −z_{12} \\ −\frac{η−z_{11}}{z_{12}(λ−η)} & \frac{1}{λ−η} \end{matrix}) .

It is not difficult to verify that vector-columns of the matrix C are eigenvectors of the matrix Z, corresponding to eigenvalues η and λ, while B = C^{−1}. Consequently,

(\begin{matrix}P_{n} & Q_{n} \\ R_{n} & T_{n} \end{matrix}) = Z^{n+1}CC^{−1} = Z^{n+1}CB =

(\begin{matrix}η^{n+1} \frac{1}{λ−η} & λ^{n+1}z_{12} \\ η^{n+1} \frac{η−z_{11}}{z_{12}(λ−η)} & λ^{n+1}(λ − z_{11}) \end{matrix}) (\begin{matrix}λ − z_{11} & −z_{12} \\ −\frac{η−z_{11}}{z_{12}(λ−η)} & \frac{1}{λ−η} \end{matrix}) .

We get from here by direct calculations the required relations for entries of the matrix Z^{n+1}.

Let us remark being easily proved claim.

Lemma 8. Every quadratic equation of the form λ^{2} + pλ + q = 0 with integer rational coefficients p and q is the characteristic equation of the unique integer (2 × 2)-matrix Z = (z_{ij}) with z_{11} = 0 and z_{12} = 1.

Proof. Evidently, the characteristic equation of every (2×2)-matrix Z = (z_{ij}); i, j = 1, 2, has the form λ^{2} + pλ + q = 0, where

p = −(z_{11} + z_{22}), q = z_{11}z_{22} − z_{12}z_{21},

and for given integer numbers p and q, integer numbers z_{ij} are defined by equalities z_{11} = 0, z_{22} = −p, z_{12} = 1, z_{21} = −q.

Further we apply the statement of Theorem 10 to matrices Z = (\begin{matrix}0 & 1 \\ −q & −p \end{matrix}), where

p, q ∈ ℤ, p^{2} − 4q ≠ 0. One can easily deduce from Theorem 10 the following

Corollary 4. Let us consider an integer (2 × 2)-matrix Z = (\begin{matrix}0 & 1 \\ −q & −p \end{matrix}) with the condition

p^{2} − 4q ≠ 0. Then the entries of the matrice

Z^{n+1} = (\begin{matrix}P_{n} & Q_{n} \\ R_{n} & T_{n} \end{matrix})

satisfy relations

R_{n} = P_{n+1}, T_{n} = Q_{n+1}, Q_{n} = \frac{λ^{n+1} − η^{n+1}}{λ − η} , P_{n+1} = −qQ_{n},  (30)
Q_{n+1} − P_{n} = −pQ_{n}, Q_{n+1} + P_{n} = λ^{n+1} + η^{n+1},  (31)

where λ and η are distinct roots of the characteristic equation λ^{2} + pλ + q = 0 of the matrix Z.

8. Generalized Fibonacci and Lucas numbers

Definition 6. The number F_{q,n}, which is equal to the number P_{n} in formulas (4) and (6), where q_{0} = 0, while all the numbers q_{i}, i ≥ 1, are equal to q, is called a generalized Fibonacci number (see [28]). The number L_{q,n} = F_{q,n−1} + F_{q,n+1} will be called a generalized Lucas number.

Remark 7. The numbers F_{n} = F_{1,n} (L_{n} = L_{1,n}) are classical Fibonacci (Lucas) numbers. The numbers F_{2,n} (L_{2,n}) are said to be Pell (Pell-Lucas) numbers, see [35], [33]. Evidently,

lim_{n→∞} \frac{F_{q,n+1}}{F_{q,n}} = lim_{n→∞} \frac{L_{q,n+1}}{L_{q,n}} = μ(q) = [q; q, q, …].

Besides Theorem 9 from the section 5, generalized golden sections and Fibonacci and Lucas numbers have some other properties, which are common for all q ∈ ℕ. We discuss in this section some of these properties.

Obviously,

μ(q) − \frac{1}{μ(q)} = [q; q, q, …] − [0; q, q, …] = q,

that is λ := μ(q) is a root of the quadratic equation

λ − \frac{1}{λ} = q ⟺ λ^{2} − qλ − 1 = 0.  (32)

It is clear that this equation is an equation of the form (25) (where one needs to set p := −q, q := −1), satisfying conditions of Theorem 3. It is easily to see that λ^{2} − qλ − 1 is the characteristic polynomial of the matrix Z := M(q) (see (7)) with the roots

λ_{1,2} = \frac{q ± \sqrt{q^{2} + 4}}{2}, λ_{1} = λ, λ_{2} = −\frac{1}{λ}.  (33)

Formulas (30) and (31) in the case under consideration imply (taking into account that P_{n} = Q_{n−1}) the equalities

F_{q,n} = \frac{λ^{n} − (−\frac{1}{λ})^{n}}{λ + \frac{1}{λ}} = \frac{1}{\sqrt{q^{2} + 4}} (μ(q)^{n} − (−\frac{1}{μ(q)})^{n}) ,  (34)

L_{q,n} = λ^{n} + (−\frac{1}{λ})^{n} = μ(q)^{n} + (−\frac{1}{μ(q)})^{n} .  (35)

The formula (34) is well-known in the particular case q = 1 (see the book [30]). It implies that

|F_{q,n} − \frac{1}{\sqrt{q^{2} + 4}}μ(q)^{n}| = \frac{1}{\sqrt{q^{2} + 4}} \frac{1}{μ(q)^{n}}  (36)

very quickly tends to zero and always less than 1/2. Analogously,

|L_{q,n} − μ(q)^{n}| = \frac{1}{μ(q)^{n}}  (37)

As a corollary, we get the rule:

Proposition 2. The generalized Fibonacci number F_{q,n} (respectively, the generalized Lucas number L_{q,n} where n ≥ 2 or q ≥ 2) is equal to the nearest integer number to the number \frac{1}{\sqrt{q^{2}+4}}μ(q)^{n} (respectively, μ(q)^{n}).

From the formula (34) we get its another version:

F_{q,n} = \frac{μ(q)^{n} − (−\frac{1}{μ(q)})^{n}}{μ(q) + \frac{1}{μ(q)}} = ∑_{k=0}^{n−1}(μ(q))^{n−1−k} (−\frac{1}{μ(q)})^{k} .  (38)

In particular, it follows from here

Proposition 3. The generalized Fibonacci number F_{q,n} is the sum of a geometric progres-

sion of the length n with the initial member μ(q)^{n−1} and with the denominator − (\frac{1}{μ(q)})^{2}.

Formulas (34) and (35) show that all the numbers f_{λ,n} := F_{q,n} (respectively, l_{λ,n} := L_{q,n}) and λ := μ(q), q ∈ ℕ, satisfy common relations

f_{λ,n} = \frac{λ^{n} − (−\frac{1}{λ})^{n}}{λ + \frac{1}{λ}} ∈ ℕ , λ > 1,  (39)

l_{λ,n} = λ^{n} + (−\frac{1}{λ})^{n} ∈ ℕ , λ > 1.  (40)

Only generalized golden sections and generalized Fibonacci and Lucas numbers, corresponding to them by formulas (39) and (40), satisfy all these relations, because these formulas for n = 2 and n = 1 give respectively

f_{λ,2} = \frac{λ^{2} − \frac{1}{λ^{2}}}{λ + \frac{1}{λ}} = λ − \frac{1}{λ} ∈ ℕ; l_{λ,1} = λ − \frac{1}{λ} ∈ ℕ ,

i.e. the equation (32) for q = f_{λ,2} = l_{λ,1}, and the equality λ = μ(q).

Formulas (7) and (10) for q_{i} = q, i ≥ 1 imply the matrix equality

(\begin{matrix}P_{n+m+1} & Q_{n+m+1} \\ P_{n+m+2} & Q_{n+m+2} \end{matrix}) = (\begin{matrix}P_{n} & Q_{n} \\ P_{n+1} & Q_{n+1} \end{matrix}) (\begin{matrix}P_{m} & Q_{m} \\ P_{m+1} & Q_{m+1} \end{matrix}) .

Therefore,

P_{n+m+1} = P_{n}P_{m} + Q_{n}P_{m+1} = P_{n}P_{m} + P_{n+1}P_{m+1}

or

F_{q,n+m+1} = F_{q,n}F_{q,m} + F_{q,n+1}F_{q,m+1}.  (41)

This formula for the case q = 1 is given in the book [30].

It’s naturally to regard that for a natural number q,

(\begin{matrix}F_{q,−2} & F_{q,−1} \\ F_{q,−1} & F_{q,0} \end{matrix}) = (\begin{matrix}P_{−2} & Q_{−2} \\ P_{−1} & Q_{−1} \end{matrix}) = (\begin{matrix}0 & 1 \\ 1 & q \end{matrix})^{−1} = (\begin{matrix}−q & 1 \\ 1 & 0 \end{matrix}) .

Then

(\begin{matrix}L_{q,−1} & L_{q,0} \\ L_{q,0} & L_{q,1} \end{matrix}) = (\begin{matrix}−q & 2 \\ 2 & q \end{matrix}) ,

(\begin{matrix}L_{q,n} & L_{q,n+1} \\ L_{q,n+1} & L_{q,n+2} \end{matrix}) = M(q)^{n+1} (\begin{matrix}−q & 2 \\ 2 & q \end{matrix}) ,  (42)

(\begin{matrix}L_{q,n+m+1} & L_{q,n+m+2} \\ L_{q,n+m+2} & L_{q,n+m+3} \end{matrix}) = M(q)^{n+1} (\begin{matrix}L_{q,m} & L_{q,m+1} \\ L_{q,m+1} & L_{q,m+2} \end{matrix}) ,

M(q)^{n+1} = (\begin{matrix}F_{q,n} & F_{q,n+1} \\ F_{q,n+1} & F_{q,n+2} \end{matrix}) .

We get from here the formula

L_{q,n+m+1} = F_{q,n}L_{q,m} + F_{q,n+1}L_{q,m+1}.  (43)

Further, we get from formulas (12) and (42) respectively

F_{q,n}^{2} = F_{q,n−1}F_{q,n+1} + (−1)^{n+1},  (44)
L_{q,n}^{2} = L_{q,n−1}L_{q,n+1} + (−1)^{n}(q^{2} + 4).  (45)

Remark 8. Formulas (30), (31), (34), and (35) show that one can consider the numbers λ, Q_{n}, and P_{n} + Q_{n+1} in formulas (30) and (31), corresponding to a Pisot matrix Z, as further generalizations of golden sections and Fibonacci and Lucas numbers.

For q = 1, 2, it is known (see [18]) a connection of the number μ(q) with the regular star-liked (q^{2} + 4)-gon. One can describe this connection as follows. Continuations of sides of the regular convex 5-gon together with its sides bounds 5 equal isosceles triangles with the proportion of (non-equal) sides μ(1) = \frac{1+\sqrt{5}}{2}. Continuations of sides of the regular convex 8-gon bounds 8 equal symmetric (relative their diagonal) 4-gons with the proportion of (non-equal) sides μ(2) = \frac{2+\sqrt{8}}{2} = 1 + \sqrt{2}.

Question 4. Is it true that for every natural number q ≥ 3, one can find symmetric quadrangles or triangles, bounded by continuations of sides of a regular convex (q^{2} + 4)-gon and having sides with the proportion μ(q)?

Remark 9. F_{5} = 5 = 1^{2} + 4, F_{6} = 8 = 2^{2} + 4, F_{7} = 13 = 3^{2} + 4.

References

[1] Arnol’d V.I., Continued fractions (Russian), M.:MCNMO, 2001, (Library ”Mathematical education”, issue 14.)

[2] Arnol’d V.I., Higher dimensional continued fractions, Regular and chaotic dynamics, V.3, N 3, 1998, pp. 10-17.

[3] Arnol’d I.V., Number theory (Russian), M.: Uchpedgiz, 1939.

[4] Bryuno A.D. and Parusnikov V.A., Comparison of various generalizations of continued fractions, Math. Notes. 61 (1997), pp. 278-286.

[5] Bukhstab A.A., Number theory (Russian), M.:Uchpedgiz, 1960.

[6] Bugaenko V.O., The Pell equations (Russian), M.:MCNMO, 2001, (Library ”Mathematical education”, issue 13.)

[7] Van der Warden B.L., Algebra I, Algebra II, Springer-Verlag, Berlin, ..., 1967, 1971.

[8] Vinogradov I.M., Foundations of the theory of numbers, Pergamon, New York, 1955.

[9] Voloshinov A.V., Mathematics and the arts (Russian), M.: Prosveschenie, 1992.

[10] Gashkov S.B. and Chubarikov V.N., Arithmetic. Algorithms. Complexity of calculations (Russian), M.:Vysshaya shkola, 2000.

[11] Gantmacher F.R., Matrix theory (Russian), M.:Nauka, 1988.

[12] Danilov V.L., Ivanova A.N., Isakova E.K., Lyusternik L.A., Salekhov G.S., Khovanskii A.N., Claf L.Ya. and Yanpol’skii A.R., Mathematical analysis. Functions, limits, series, continued fractions (Russian), M.:Fizmatgiz, 1961.

[13] Idel’son N.I., Calendar history, Essays on history of celestial mechanics (Russian), M.: Nauka, 1975, pp. 308-411.

[14] Cassels J.W.S, An introduction to diophantine approximation, Cambridge University Press, 1957.

[15] Klein F. Elementarmathematik vom hoheren standpunkte aus erster band.Arithmetik. Algebra. Analysis. Springer-Verlag, Berlin, 1924.

[16] Coxeter H.S.M., Moser W.O.J., Generators and relations for discrete groups, Springer-Verlag, Berlin, ..., 1972.

[17] Markov A.A., Lectures on continued fractions (Russian), Selected proceedings on theory of continued fractions and function theory, least deviated from zero, M.–L.: Gostekhizdat, 1948.

[18] Pedoe D., Geometry and the liberal arts, Penguin Books Ltd., Harmondsworth, 1976.

[19] Pustyl’nikov L.D., Generalized continued fractions and ergodic theory, Russian Math. Surveys, 2003, 58(1), pp. 109-159.

[20] Stieltjes T.-I. Recherches sur les fractions continues, Annales de la Faculte des Sciences de Toulouse (tome VIII, 1894, pp. 1-122; tome IX, 1895, pp. 1-47).

[21] Khinchin A.Ya. Continued fractions, Univ. Chicago Press, Chicago-London, 1964.

[22] Khovanskii A.N. Application of continued fractions and their generalizations to questions of approximation analysis (Russian), M.: Gostekhizdat, 1956.

[23] Chebotarev N.G. Theory of continued fractions (Russian), Kazan’, 1938.

[24] Shilov G.E., Simple scale. Construction of musical scale (Russian), M.: Nauka, 1980, (Popular lectures on mathematics. Issue 37.)

[25] Berend D., Frougny C., Computability by finite automata and Pisot bases, Math. Systems Theory, 1994, V.27, pp. 275-282.

[26] Bertin M.J., Decomps-Guilloux A., Grandet-Hugot M., Pathiaux-Delefosse M., Schreiber J.P., Pisot and Salem numbers, Birkhäuser, Basel, 1992.

[27] Boyd D.W., Mauldin R.D., The order type of the set of Pisot numbers, Top. Appl., 1996, V.69, pp.115-120.

[28] Bradley S., A geometric connection between generalized Fibonacci sequences and nearly golden section, Fibonacci Q., 2000, V.38, N 2, pp. 174-179.

[29] Bugeaud Y., On a property of Pisot numbers and related questions, Acta Math. Hungar., 1996, V.73, N 1-2, pp. 33-39.

[30] Graham R., Knuth D., Patachnik O., Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.

[31] Hardcastle D.M., Khanin K., Continued fractions and the d-dimensional Gauss transformation, Comm. Math.Phys., 2001, V.215, N 3, pp. 487-515.

[32] Koksma J.F., Ein mengentheoretischer Satz über die Gleichverteilung modulo Eins, Compos. Math., 1935, V.2, pp.250-258.

[33] Koshy T., Fibonacci and Lucas numbers with Applications, Wiley-Interscience, 2001.

[34] Lewis J., Zagier D., Period functions and the Selberg zeta function for the modular group, In: The Mathematical Beauty of Physics, Adv. Series in Math. Physics 24, World Scientific, Singapore, 1997, pp. 83-97.

[35] Melham R., Sums involving Fibonacci and the Pell numbers, Portugaliae Mathematica, 1999, V.56, N 3, pp.309-317.

[36] Nogueira A., The Borel-Bernstein theorem for multidimensional continued fractions, J. Anal. Math., 2001, V.85, pp. 1-41.

[37] Pisot Ch., La répartition modulo 1 et les nombres algébriques (Thèse), Ann. Sc. Norm. Sup. Pisa, 1938, II. Ser. 7, pp. 205-248.

[38] Vulakh L.Ya., Units in some families of algebraic fields, Trans. Amer. Math. Soc., 2004, V. 356, pp. 2325-2348.

Berestovskii Valerii Nikolaevich Omsk Branch of Sobolev Institute of Mathematics SO RAN Pevtsova 13, 644099, Omsk, Russia

   E-mail address: berestov@iitam.omsk.net.ru

Nikonorov Yurii Gennadievich Rubtsovsk Industrial Institute of Altai State Technical University after I.I. Polzunov Traktornaya 2/6, 658207, Rubtsovsk, Russia

   E-mail address: nik@inst.rubtsovsk.ru