# Integer Semigroups Associated with Dumont-Thomas Numeration Systems

Authors: Víctor F. Sirvent
Journal: ISRN Combinatorics
 (2014)

---

## Abstract

Given a primitive substitution, we define different binary operations on infinite subsets of the nonnegative integers. These binary operations are defined with the help of the Dumont-Thomas numeration system; that is, a numeration system associated with the substitution. We give conditions for these semigroups to have an identity element. We show that they are not finitely generated. These semigroups define actions on the set of positive integers. We describe the orbits of these actions. We also estimate the density of these sets as subsets of the positive integers.


---

## Body

## 1. Introduction

Integer semigroups have been studied in different contexts (cf. [1–4]). One of the well known binary operations is the Fibonacci multiplication, introduced by Knuth [1]. This operation is related to the dynamical system obtained by the Fibonacci substitution (cf. [3]). It has been generalized in different ways to the tribonacci substitution; see [4–6]. The author studied the usage of binary operations on the set of nonnegative integers, in order to describe the self-similar structure of the k-bonacci substitutions [4] and on the so-called flipped tribonacci substitution [7].In the present article, we introduce binary operations on infinite subsets of the nonnegative integers so that they are integer semigroups. These binary operations are associated with a substitution, in particular to the numeration system defined by the substitution, the so-called Dumont-Thomas numeration system. These numeration systems play an important role in the study of Rauzy fractals; for details see [8, 9] and references within. The integer semigroups defined in the paper, in general, do not have identity elements. We explore when they have identity elements. In Theorem 3, we show that these semigroups are not finitely generated.Moreover, we show that these semigroups define actions on the set of positive integers, and we describe the orbits of these actions.In Section4, we study the density of these semigroups as subsets of the positive integers.


## 2. Substitutions and Automata

A substitution on a finite alphabet𝒜
=
{
1
,
…
,
k
} is a map ζ from 𝒜 to the set of finite words on 𝒜; that is, 𝒜
*
=
∪
i
≥
0
𝒜
i. This map extends to 𝒜
* by concatenation by ζ
(
∅
)
=
∅ and ζ
(
U
V
)
=
ζ
(
U
)
ζ
(
V
), for all U, V
∈
𝒜
*. Let A
ℕ denote the set of one-sided infinite sequences in 𝒜. The map ζ is extended to 𝒜
ℕ in the obvious way. We call u
∈
𝒜
ℕ a fixed point of ζ if ζ
(
u
)
=
u and periodic if there exists l
>
0 so that it is fixed for ζ
l. There is a dynamical system associate to the sequence u, called substitution dynamical system; for details see [8–10].Theincidence matrix of the substitution ζ is defined as the matrix M
=
(
M
i
j
) whose entry M
i
j is the number of occurrences of the symbol j in the word ζ
(
i
), for 1
≤
i
,
j
≤
k. We say the substitution is primitive if its incidence matrix is primitive; that is, all the entries of M
l are positive for some l
>
0. We shall assume throughout the paper that the substitutions are primitive.For a primitive substitution there are a finite number of periodic points. So, we can assume without loss of generality that a primitive substitution has a fixed point; sayu
=
u
1
u
2
⋯ and u
1
=
1; that is, the first symbol of ζ
(
1
) is 1.LetW
⊂
𝒜
*
=
∪
i
≥
0
𝒜
i be a set of finite words on the alphabet 𝒜
=
{
1
,
…
,
k
}. An automaton over 𝒜, 𝔄
=
(
Q
,
W
,
E
,
I
) is a direct graph labelled by elements of 𝒜. Q is the set of states, I
⊂
Q is the set of initial states, W is the set of labels, and E
⊂
Q
×
W
×
Q is the set of labelled edges or transitions. If (
p
,
w
,
q
)
∈
E, we say that w is a transition between p and q.Theprefix automaton of the substitution ζ (cf. [11]) is the automaton 𝔄
=
(
Q
,
W
,
E
,
I
) so that one has the following.(i)
Q
=
𝒜.
(ii)
W
=
Pref, the set of proper prefixes of the words ζ
(
p
), for p
∈
𝒜. We will denote by e the empty prefix.
(iii)
(
p
,
w
,
q
) is in E if p, q are elements of 𝒜, w
∈
W and w
q is a prefix of ζ
(
p
).
(iv)
I
=
{
1
}.In Figure1, it is shown the prefix automaton of the k-bonacci substitution; that is, ζ
(
1
)
=
12
,
ζ
(
2
)
=
13
,
…
,
ζ
(
k
-
1
)
=
1
k, and ζ
(
k
)
=
1.Figure 1
Thek-bonacci automaton.The automaton reads words from left to right. Afinite path in the automaton, 𝔄, is word in E, the set of transitions:
(1)
(
p
m
,
a
m
,
q
m
)
(
p
m
-
1
,
a
m
-
1
,
q
m
-
1
)
⋯
(
p
0
,
a
0
,
q
0
)
such that q
i
=
p
i
-
1 for 1
≤
i
≤
m and p
m
∈
I; however, we usually denote the paths using only the labels, that is, a
m
⋯
a
0. We say that the path a
m
⋯
a
0
terminates at the state q
0 and we say that the path passes through the state
q, if there is i
∈
{
0
,
…
,
m
} such that p
i
=
q, in (1). See [12] for more details on automata theory.Theorem 1 (see [11, 13]).
LetU be a nonempty prefix of u, the fixed point of the substitution ζ. Then there exists a unique path on the prefix automaton of ζ: a
n
a
n
-
1
⋯
a
0 such that a
n
≠
e and U
=
ζ
n
(
a
n
)
ζ
n
-
1
(
a
n
-
1
)
⋯
ζ
(
a
1
)
a
0. Conversely, to any such path, there corresponds a prefix of u, given by the above formula.Due to this theorem, we can associate numeration systems for the positive integers, in the following way. Letn be a positive integer and U the prefix of length n of u; we define ϵ
:
ℕ
→
W
*, by ϵ
(
n
)
=
a
l
a
l
-
1
⋯
a
1
a
0, where a
l
≠
e and U
=
ζ
l
(
a
l
)
ζ
l
-
1
(
a
l
-
1
)
⋯
ζ
(
a
1
)
a
0. Moreover, this representation is unique. This numeration system is called the Dumont-Thomas numeration system associated with the substitution ζ (cf. [13, 14]). For general theory of numeration systems see [8, 14–18].


## 3. Semigroups

We consider the following subset of positive integers:(2)
𝒫
:
=
{
n
∈
ℕ
:
ϵ
(
n
)
=
a
l
⋯
a
0
,
such
that
a
l
⋯
a
0
is
path
in
𝔄
terminating
at
state
1
}
.We define “⋆”, a binary operation in 𝒫, in the following way: let n
,
m
∈
𝒫 such that ϵ
(
n
)
=
a
l
a
l
-
1
⋯
a
1
a
0 and ϵ
(
m
)
=
b
r
b
r
-
1
⋯
b
0, so
(3)
ϵ
(
n
⋆
m
)
:
=
a
l
a
l
-
1
⋯
a
1
a
0
b
r
b
r
-
1
⋯
b
0
.
This binary operation is well defined since the paths in the prefix-automaton, associated with the elements of 𝒫, terminate at the initial state, so we can concatenate them. It is clear that the operation ⋆ is associative. Hence, (
𝒫
,
⋆
) is a semigroup.However, the binary operation⋆ is not always commutative; for example, in the Fibonacci case, we consider ϵ
(
2
)
=
1
e and ϵ
(
3
)
=
1
e
e, so ϵ
(
2
⋆
3
)
=
1
e
1
e
e
=
ϵ
(
10
) and ϵ
(
3
⋆
2
)
=
1
e
e
1
e
=
ϵ
(
9
), so 2
⋆
3
=
10 and 3
⋆
2
=
9.If the wordζ
(
1
) starts with the symbol 1, then in the prefix automation the transition (
1
,
e
,
1
) is allowed, so e
⋯
e
a
l
a
l
-
1
⋯
a
1
a
0 is a path in 𝔄, and
(4)
ζ
l
(
a
l
)
ζ
l
-
1
(
a
l
-
1
)
⋯
ζ
(
a
1
)
a
0
=
ζ
l
+
i
(
e
)
⋯
ζ
l
+
1
(
e
)
ζ
l
(
a
l
)
ζ
l
-
1
(
a
l
-
1
)
⋯
ζ
(
a
1
)
a
0
.
By convention we say that ϵ
(
0
)
=
e and let 𝒫
′
=
𝒫
∪
{
0
}. Clearly 0
⋆
n
=
n, but n
⋆
0
≠
n; since ζ
l
(
a
l
)
ζ
l
-
1
(
a
l
-
1
)
⋯
ζ
(
a
1
)
a
0, it does not have to be ζ
l
+
1
(
a
l
)
ζ
l
(
a
l
-
1
)
⋯
ζ
2
(
a
1
)
ζ
(
a
0
). Hence, the pair (
𝒫
′
,
⋆
) has a left identity. If n
≠
0 and ϵ
(
n
)
=
a
l
a
l
-
1
⋯
a
1
a
0, we always consider that a
l
≠
e. However (
𝒫
'
,
⋆
) is not a semigroup; consider ϵ
(
n
⋆
(
e
⋆
m
)
)
=
a
l
⋯
a
0
b
r
⋯
b
0; since e
⋆
m
=
m and on the other hand ϵ
(
(
n
⋆
e
)
⋆
m
)
=
a
l
⋯
a
0
e
b
r
⋯
b
0, therefore n
⋆
(
e
⋆
m
)
≠
(
n
⋆
e
)
⋆
m. The algebraic structure of the pair (
𝒫
′
,
⋆
) is an unital, a set with a closed binary operation with identity; see [19].We shall change the definition of the binary operation so that we have a semigroup with identity. Without loss of generality, we can suppose that the substitutionζ is of the form ζ
(
1
)
=
1
w
2
w
′, where w
′ is a finite word on the alphabet 𝒜 and w
=
e or w
=
1
⋯
1; that is, w is the empty word or a word consisting only of a concatenation of the symbol 1. Let 𝒫
+ be the set of natural numbers n whose representation is ϵ
(
n
)
=
a
l
⋯
a
1
a
0, where the a
l
⋯
a
0 is a path in 𝔄 that starts in the initial state and terminates in the state 2 and the path a
l
⋯
a
1 terminates at the initial state.We can think of the set𝒫
+ as the set of numbers whose representation is a path in the prefix-automaton that starts in the state 1 and terminates in the state 2, such that it passes through 1 in the step before terminating.We define a binary operation “⋄” on 𝒫
+ as follows. Let n
,
m
∈
𝒫
+, whose representations are ϵ
(
n
)
=
a
l
⋯
a
1
a
0 and ϵ
(
m
)
=
b
r
⋯
b
1
b
0; so
(5)
ϵ
(
n
⋄
m
)
:
=
a
l
a
l
-
1
⋯
a
1
b
r
⋯
b
0
.
This binary operation is well defined since it is an element of 𝒫
+. The operation ⋄ is associative. Let n
,
m
,
t
∈
𝒫
+ such that ϵ
(
n
)
=
a
l
⋯
a
1
a
0, ϵ
(
m
)
=
b
r
⋯
b
1
b
0 and ϵ
(
t
)
=
c
s
⋯
c
1
c
0; so
(6)
ϵ
(
n
⋄
(
m
⋄
t
)
)
=
(
a
l
⋯
a
1
a
0
)
⋄
(
b
r
⋯
b
1
c
s
⋯
c
0
)
=
a
l
⋯
a
1
b
r
⋯
b
1
c
s
⋯
c
0
,
ϵ
(
(
n
⋄
m
)
⋄
t
)
=
(
a
l
⋯
a
1
b
r
⋯
b
1
b
0
)
⋄
(
c
s
⋯
c
0
)
=
a
l
⋯
a
1
b
r
⋯
b
1
c
s
⋯
c
0
.The semigroup(
𝒫
+
,
⋄
) has a left identity; however, there might not be more than one left identity element. Let (
1
,
β
,
2
) be any transition in the prefix automaton 𝔄 from the state 1 to the state 2, and κ
∈
ℕ such that ϵ
(
κ
)
=
β. By definition κ
∈
𝒫
+ and κ
⋄
n
=
n, for any n
∈
𝒫
+. In general (
𝒫
+
,
⋄
) does not have a right identity.Proposition 2.
Letζ be a primitive substitution on 𝒜 such that ζ
(
1
)
=
1
w
2
w
′ where w
=
1
⋯
1 or w
=
e and w
′ is a finite word on the alphabet. If the symbol 2 does not belong to the word w
′, then the identity of the semigroup (
𝒫
+
,
⋄
) is the element ι of 𝒫
+ whose representation is ϵ
(
ι
)
=
α, with α
=
1
w if w
≠
e, or α
=
1, if w
=
e.Proof.
Letα
=
1
w if w
≠
e, or α
=
1, if w
=
e. We remark that α is a proper prefix of ζ
(
1
), so α
∈
Pref, and (
1
,
α
,
2
)
∈
E in the prefix automaton; that is, α is a transition from the state 1 to the state 2. Since w
′ does not have the symbol 2, α is the only transition in the prefix automaton from the state 1 to 2. The transition in the automaton 𝔄 from the initial state to itself and from the state 1 to the state 2 are shown in Figure 2; in this figure we suppose that the word w
′ does not contain the symbol 1.
Letn
∈
𝒫
+ with ϵ
(
n
)
=
b
l
⋯
b
1
b
0. We have ϵ
(
n
⋄
ι
)
=
b
l
⋯
b
1
α. Since n
∈
𝒫
+, b
0 is a transition from the state 1 to 2 and there is only one transition from state 1 to state 2, so b
0
=
α. Hence, n
⋄
ι
=
n. On the other hand, ι is a left identity, as it was pointed out before.Figure 2
Part of the automaton described in the proof of Proposition2.We remark thatι
=
1 if and only if w is the empty word. For example, this is the situation in the k-bonacci substitutions.We say that a semigroup(
𝒮
,
⋆
) is finitely generated if there exists 𝔊
=
{
s
1
,
…
,
s
m
} with s
i
∈
𝒮 such that for all s
∈
𝒮 we have s
=
s
i
1
⋆
⋯
⋆
s
i
l, for some l and s
i
j
∈
𝔊, 1
≤
j
≤
l. The elements of 𝔊 are called generators of (
𝒮
,
⋆
).We remark that in the Fibonacci case, the set(
𝒫
,
⋆
) is not finitely generated because we have the paths 1
e
,
1
e
e
,
1
e
e
e
,
… that correspond to elements in 𝒫 but the word e is not in 𝒫. Similarly the semigroup (
𝒫
+
,
⋄
) is not finitely generated; considering the paths 1
e
⋯
e
︸
l
1, with l
≥
1, the numbers associated with these paths cannot be finitely generated since ϵ
(
e
) is not in 𝒫
+. The following theorem shows that this is a general situation.Theorem 3.
The semigroups(
𝒫
,
⋆
) and (
𝒫
+
,
⋄
) are not finitely generated.Proof.
We suppose, as before, thatζ
(
1
)
=
1
w
2
w
′, where w
=
e or w
=
1
⋯
1
︸
r, with r
≥
1, and w
′ is a finite word in the alphabet. Let α
:
=
1
w if w
≠
e or α
:
=
1 if w
=
e. It is a proper prefix of ζ
(
1
) and (
1
,
α
,
2
) is a transition in the prefix automaton. Let a
l
⋯
a
1 be a path in the prefix automaton such that it starts and ends at the state 1 so that a
l
⋯
a
s does not terminate at the state 1, for 1
<
s
≤
l. Let m be the number in 𝒫
+, such that ϵ
(
m
)
=
a
l
⋯
a
1
a
0, with a
0
=
α. We consider the numbers n
l
=
ϵ
(
a
l
⋯
a
1
e
⋯
e
︸
l
α
), with l
≥
1; by definition they belong to 𝒫
+. These numbers cannot be finitely generated, in fact. Let us consider n
1; if we want to write it as n
1
=
m
⋄
t
1, then t
1 has to be of the form ϵ
(
t
1
)
=
e
α, but this is not a representation given by the Dumont-Thomas numeration system, since the first symbol is e. There is no other possible “factorization” of n
1, since ϵ
(
a
l
⋯
a
s
)
∉
𝒫
+ for 1
≤
s
≤
l. Therefore, n
1 cannot be written as product of 𝒫
+, different from itself, and the identities. Similar argument holds for n
l for l
>
1. Therefore, (
𝒫
+
,
⋄
) is not finitely generated.
The proof that(
𝒫
,
⋆
) is not finitely generated follows in a similar manner.We generalize the classical concepts of prime and composite numbers into this context. We say that an elementm of 𝒫
+ is 𝒫
+
-composite if there exist n
,
n
′
∈
𝒫
+ different of an identity element such that m
=
n
⋄
n
′. We say that m is 𝒫
+
-prime if it is not composite. In the proof of Theorem 3, we have shown that the numbers n
l are 𝒫
+-primes.Corollary 4.
The numberm
∈
𝒫
+ is 𝒫
+-prime if and only if ϵ
(
m
)
=
a
l
⋯
a
0 where a
l
⋯
a
0 is a path in the automaton 𝔄 with the property that a
l
⋯
a
s does not terminate at the state 1 for 1
<
s
<
l.Proof.
Letm
∈
𝒫
+ whose Dumont-Thomas representation is ϵ
(
m
)
=
a
l
⋯
a
0 where a
l
⋯
a
0 is a path in 𝔄 such that a
l
⋯
a
s does not terminate at the state 1 for 1
<
s
<
l. So the numbers n
s given by ϵ
(
n
s
)
=
a
l
⋯
a
s are not in 𝒫. Since the representation is unique, there are not n
,
n
′
∈
𝒫
+
∖
{
e
} such that m
=
n
⋄
n
′. Hence m is 𝒫
+-prime.
On the other hand, letm be 𝒫
+-prime such that ϵ
(
n
)
=
a
l
⋯
a
0. If there is a 2
≤
r
≤
l
-
1 such that a
l
⋯
a
r is a path in 𝔄 that terminates at the state 1, then m
=
m
1
⋄
m
2, where ϵ
(
m
1
)
=
a
l
⋯
a
r
α, ϵ
(
m
2
)
=
a
r
-
1
⋯
a
0, and (
1
,
α
,
2
) is a transition in the automaton from the state 1 to the state 2. By construction m
1 and m
2 are in 𝒫
+; therefore, m could not be prime.We point out that the semigroup𝒫
+ acts on the set of the positive integers. Let n
∈
𝒫
+, and m
∈
ℕ; we suppose that m
∉
𝒫
+. If ϵ
(
n
)
=
a
l
⋯
a
1
a
0 and ϵ
(
m
)
=
b
r
⋯
b
0, where b
r
⋯
b
0 is a path in the prefix automaton, 𝔄, that terminates at the state q, thena
l
⋯
a
1
b
r
⋯
b
0 is a path in 𝔄, which starts at the initial state and terminates at the state q. So n
⋄
m is defined and ϵ
(
n
⋄
m
)
=
a
l
⋯
a
1
b
r
⋯
b
0; however, n
⋄
m is not in 𝒫
+, if q
≠
2. Let ϕ
n
:
ℕ
→
ℕ be the map defined by ϕ
n
(
m
)
:
=
n
⋄
m. This map defines a left action of 𝒫
+ on ℕ, since ϕ
κ is the identity, where κ is a left identity of 𝒫
+, and ϕ
n
∘
ϕ
n
′
=
ϕ
n
⋄
n
′.The dynamics of this action can be studied. Letm
∈
ℕ; the orbit of
m
under
𝒫
+ is the set {
ϕ
n
(
m
)
:
n
∈
𝒫
+
}, which is denoted by 𝒫
+
⋄
m. Similarly we define the orbit of m under (
𝒫
,
⋆
). The following proposition shows how the orbits of both actions are related.Proposition 5.
Letm be a positive integer. Then 𝒫
+
⋄
m
=
(
𝒫
⋆
m
)
∪
{
m
}.Proof.
Letϵ
(
m
)
=
b
r
⋯
b
0 be the representation of m, where b
r
⋯
b
0 is a path in the automaton 𝔄 that starts in the initial state and terminates at the state p. Let t
≠
m be an element of 𝒫
+
⋄
m, so t
=
n
⋄
m, for some n
∈
𝒫
+, with ϵ
(
n
)
=
a
l
⋯
a
1
a
0, and l
≥
1; so ϵ
(
n
⋄
m
)
=
a
l
⋯
a
1
b
r
⋯
b
0. Since a
l
⋯
a
1 is a path in the automaton that starts and terminates at the initial state, we have t
=
n
′
⋆
m, where ϵ
(
n
′
)
=
a
l
⋯
a
1. If t
=
m, then m
=
κ
⋄
m, where ϵ
(
κ
)
=
a
0, with (
1
,
a
0
,
2
) being a transition between the states 1 and 2. Hence 𝒫
+
⋄
m
⊂
(
𝒫
⋆
m
)
∪
{
m
}.
Lets
∈
𝒫
⋆
m, since (
𝒫
,
⋆
) does not have identity s
≠
m. So s
=
n
⋆
m, for some n
∈
𝒫. Let ϵ
(
n
)
=
c
l
⋯
c
0 where c
l
⋯
c
0 is a path in the automaton that starts and terminates at the initial state. Hence, ϵ
(
s
)
=
c
l
⋯
c
0
b
r
⋯
b
0. Let n
′ be an element of 𝒫
+, whose representation is ϵ
(
n
′
)
=
c
l
⋯
c
0
α, where (
1
,
α
,
2
) is a transition from the state 1 to 2. So n
′
⋄
m
=
n. Therefore, 𝒫
⋆
m
⊂
𝒫
+
⋄
m. Clearly m
∈
𝒫
+
⋄
m, since m
=
κ
⋄
m, where ϵ
(
κ
)
=
α.A further step in the study of the dynamics of this action is the characterization of its invariant sets. The setY
⊂
ℕ is (
𝒫
+
,
⋄
)
-invariant if ∪
y
∈
Y
𝒫
+
⋄
y
=
Y.


## 4. Density of the Semigroups

In this section, we will study the density of the sets𝒫 and 𝒫
+ in the set of positive integers. Let λ be the Perron-Frobenius eigenvalue of M and υ and ω the right and left nonnegative eigenvectors associated with λ; that is, M
υ
=
λ
υ, ω
T
M
=
λ
ω
T. If we choose them so that ω
T
v
=
∑
i
=
1
k
‍
υ
i
ω
i
=
1, then the matrix υ
ω
T is called the Perron projection of M (cf. [20, 21]).Proposition 6.
An estimation of the density of𝒫 in the set of positive integers is given by
(7)
lim
⁡
sup
⁡
N
→
∞
1
N
#
{
m
∈
𝒫
:
m
≤
N
}
≤
ω
1
ω
1
+
⋯
+
ω
k
,
where ω
=
(
ω
1
,
…
,
ω
k
) is the left positive eigenvector, associated with Perron-Frobenius eigenvalue, of the transition matrix M.Proof.
LetM
i
j
(
n
) be the (
i
,
j
) entry of the matrix M
n. The number of paths of length n in 𝔄 that start in the state i and end in the state j is given by M
i
j
(
n
).
LetR
(
n
) be the number of paths of length n in the automaton 𝔄 that start at the initial state; that is, R
(
n
)
=
∑
j
=
1
k
‍
M
1
j
(
n
). By the Perron-Frobenius Theorem for primitive matrices lim
⁡
n
→
∞
M
n
λ
-
n
=
v
w
T (cf. [21]). So the asymptotical growth of R
(
n
) is given by lim
⁡
n
→
∞
R
(
n
)
λ
-
n
=
∑
j
=
1
k
‍
(
υ
ω
T
)
1
j.
LetP
(
n
) be the number of paths of length n in 𝔄, that start in the state 1 and terminate in the state 1, so P
(
n
)
=
M
11
(
n
). So its asymptotical growth is given by lim
⁡
n
→
∞
P
(
n
)
λ
-
n
=
(
υ
ω
T
)
11. Therefore
(8)
lim
⁡
sup
⁡
N
→
∞
1
N
#
{
m
∈
𝒫
:
m
≤
N
}
≤
lim
⁡
n
→
∞
P
(
n
)
R
(
n
)
=
lim
⁡
n
→
∞
P
(
n
)
λ
-
n
R
(
n
)
λ
-
n
=
(
υ
ω
T
)
11
∑
j
=
1
k
(
υ
ω
T
)
1
j
.
This expression simplifies in the following way:(9)
(
υ
ω
T
)
11
∑
j
=
1
k
(
υ
ω
T
)
1
j
=
υ
1
ω
1
∑
j
=
1
k
υ
1
ω
j
=
ω
1
ω
1
+
⋯
+
ω
k
.We prove in a similar manner the corresponding result for𝒫
+.Corollary 7.
An estimation of the density of𝒫
+ in the set of positive integers is given by
(10)
lim
⁡
sup
⁡
N
→
∞
1
N
#
{
m
∈
𝒫
+
:
m
≤
N
}
≤
ω
2
ω
1
+
⋯
+
ω
k
,
where ω
=
(
ω
1
,
…
,
ω
k
) is as in Proposition 6.Example 8.
In the tribonacci case, the transition matrix is(11)
M
=
(
1
1
0
1
0
1
1
0
0
)
.The Perron-Frobenius eigenvalue isλ, the real root of the polynomial x
3
-
x
2
-
x
-
1. The left eigenvector of M is (
α
,
α
2
,
α
3
), where α
=
λ
-
1 and the right eigenvector of M is (
α
2
,
α
3
+
α
4
,
α
3
), without normalization. According to Proposition 6 and Corollary 7, the upper bound of the density of 𝒫 is α
≈
0.5436 and that of 𝒫
+ is α
2
≈
0.2955.



---

*Source: 275260-2014-01-23.xml*