and 
The idea to examine the relations between the lengths of and
is not new. For example, the special case 
has been studied in [11].
are even, there is nothing to prove. Otherwise, we
have 
and 
.
And the conclusion follows from 
.
, not a perfect
square, 
is 
-conjugated to 
. For all 
,
is -conjugated to either or 
.
Using notations 3.10, we have:
and 
. Then, by proposition 4.4, we have:
.
But 
can be written as 
, where 
and, using again 4.4, the matrix 
belongs to 
. This matrix verifies
also the other prerequisites of proposition 3.7,
so that 
for some 
. Similarly, we have
.
If 
is even, 
can be written as 
, where
. Thus 
and, as above, 
for some 
. This leads to 
.
Applying theorem 2.6, we obtain 
and therefore 
.
In the remaining case ( odd), lemma 5.1
shows that 
.
From proposition 3.7, 
for some . Applying again theorem 2.6,
we obtain 
. Since 
is not possible,
we have 
i.e. 
.
, not a square, 
.
(letters) the set 
where
where 
,
we will call 
and 
(respectively) "
"
and "
".
and the parity of 
,
it exists one and only one suffix such that 
.
Moreover, the following formulae hold for the remaining six possibilities:
be a pattern, 
be a permutation of and 
an odd integer such that all
three matrices 
belong to 
. Then 
and 
don't occur while
the remaining possibilities are characterized by
according to the rules:
| actual state | ABC | ACB | BAC | BCA | CAB | CBA |
next state when  is even |
CBA | CAB | BCA | BAC | ACB | ABC |
| next state when is odd |
BCA | BAC | CBA | CAB | ABC | ACB |
When the input list is the period of a quadratic integer 
and
the initial state chosen as 
, we will shorten
the notations to 
.
.
:
(i) The final state (say ) can only be 
, 
or 
.
(ii) Defining 
when 
, 
(the concatenation of the three lists 
, 
and 
)
when 
and when 
,
the period of is 
.
(iii) The case 
in theorem 5.2
is nothing but while 
is 
.
are only occurring
with quadratic integers of first kind. The remaining three possibilities
are the even permutations of .
Assertion (ii) follows from the way the transition table has been
built. Equations 5.3 have all the form 
and the algorithm consists into finding prefixes and suffixes such
that any 
is an integer (or a sequence of integers),
the internal prefixes and suffixes canceling according to 
.
And we have:
(so that 
by lemma 4.13) and , leading
to 
so that 
by theorem 5.2. But, by 5.3,
starts by 
and ends by 
(when
is even) or by 
when 
is odd. The zeroes occurring in (if any) are
only internal and can be removed by using .
Thus 
is a list of positive integers
and the unique factorization theorem 2.6 applies
to 
, proving that
is (in this case) the period of the confrac expansion of .
In the case and, for example, , we cannot have
. By theorem
5.2, we have:
don't start or end by a zero, leading to
the same conclusion as above.
When 
, list ever ends by 
and we
have (whatever the ending state can be):
is either 
or 
, 
and
. The conclusion follows since
is the identity matrix.
can be interpreted as follows. When
building , automaton translates 
into 
so that a two places rotation of gives a sequence beginning
by 
that leads, after reduction,
to a sequence starting by 
as it should be (lemma
4.13).
but 
instead
of 
. The rules for state transitions remain the same,
and the output rules are now:
such that 
,
the final state (say ) of can only be , 
or 
.
And we have
|
 |
 |
 |
 |
|
 |
 |
0 |  |
|
|
 |
1 |  |
|
-1 |  |
0 | |
|
-1 |  |
1 | |
and use 
when 
is odd, while we start
and stop in state 
and use 
when is even.
be or and 
be positive integers
such that
such that
we have 
and, for all
other 
, the period length of 
and 
obey to relations 5.5.
. 
and equality holds if and only if no zeroes occur, i.e. when .
When 
(i.e. when 
is odd), we have exactly 
since any quotient leads to exactly five numbers (what depends on
the internal state is the way these numbers are affected to the three
output lists).
When is even, automaton ends in state , and 
.
Therefore any quotient generates at most three quotients.
In order to maximize 
, we have to go in state
as soon as possible (implying 
to be odd) and then remain
in this state (implying others 
to be even). In any case,
the first two quotients generate only two quotients,
leading to the 
in inequality (2).
.
Since the first quotient is ever even, it follows from 5.4
that 
. Again from 5.4,
assuming that , 
can only be
achieved when all the 
are even and at least 
, leading
to an "any, one, one" pattern for (and therefore
). The special case appears from the fact that 
collapses into 
(and therefore ).
, we have 
.
Apart from , inequality (1) i.e. 
ever holds.
When, additionally 
, (1) can be refined into 
.
and obtain 
by substituting all 
by 
and all 
by
, other quotients remaining the same. Choosing 
,
we have 
from 
and lemma 5.15. Thus 
. Going
back to from introduces two zeroes in
and a -decrease of 
, while going back to
from introduces one zero in and a 
-decrease
of . From the palindromic property and the fact that middle
element is odd or none, the occur by pairs, proving the
first affirmation.
In order to obtain 
, the maximal length
should decrease by 
. This can only happens if all quotients,
including , were . But 
implies . Otherwise
, i.e. (1) holds and equality implies that 
is a "nothing
but ones" pattern. From proposition 4.15,
such a pattern leads to when 
: in this case
is forbidden and we must have .
. When, additionally 
then (4) can be refined into 
.
, obtain 
by substituting all 
by 
and all 
by
(other quotients remaining the same) and choose 
.
It follows from 5.13 that at each stage
input+output is 
or 
so that 
.
Therefore 
. The eventual difference
between 
and 
is caused by occurrence
of zeroes in . But is palindromic, and it's middle
element cannot be 0 from corollary 4.11 : the
zeroes occur by pairs and 
is proven.
From the proof of lemma 5.15, equality occurs in (4) when
is odd, and the other 
are even. But the middle
element of can only be odd or none. Therefore 
is forbidden when 
is even.
, the following table describe how to construct an
such that and have the requested length. Column
gives a pattern such that 
. When substituting a palindromic
pair of non-middle by a pair of , 
decrease by
. When substituting a middle by or a pair of by
a pair of , decrease by . When 
,
this -decrease can be achieved by a substitution 
acting over a well chosen pair.
case, the descent from 
down to 
is easier to describe when split into two overlapping processes, the
first one descending from down to 
:
down to .
and 
completes
the proof.
, and 
has a middle element 
then
and 
(in the general case,
is even or none). . has also a
middle element, 
. From , is
"any, one, one" and 
.
, we have
by 
.
.
and equality occur
iff