Spectral properties of partial automorphisms of a binary rooted tree
We study asymptotics of the spectral measure of a randomly chosen partial automorphism of a rooted tree. To every partial automorphism x we assign its action matrix Ax. It is shown that the uniform distribution on eigenvalues of Ax converges weakly in probability to δ₀ as n → ∞, where δ₀ is the delt...
Saved in:
| Date: | 2018 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | English |
| Published: |
Інститут прикладної математики і механіки НАН України
2018
|
| Series: | Algebra and Discrete Mathematics |
| Online Access: | http://dspace.nbuv.gov.ua/handle/123456789/188414 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Spectral properties of partial automorphisms of a binary rooted tree / E. Kochubinska // Algebra and Discrete Mathematics. — 2018. — Vol. 26, № 2. — С. 280–289. — Бібліогр.: 6 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-188414 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1884142023-02-28T01:27:07Z Spectral properties of partial automorphisms of a binary rooted tree Kochubinska, E. We study asymptotics of the spectral measure of a randomly chosen partial automorphism of a rooted tree. To every partial automorphism x we assign its action matrix Ax. It is shown that the uniform distribution on eigenvalues of Ax converges weakly in probability to δ₀ as n → ∞, where δ₀ is the delta measure concentrated at 0. 2018 Article Spectral properties of partial automorphisms of a binary rooted tree / E. Kochubinska // Algebra and Discrete Mathematics. — 2018. — Vol. 26, № 2. — С. 280–289. — Бібліогр.: 6 назв. — англ. 1726-3255 2010 MSC: 20M18, 20M20,05C05. http://dspace.nbuv.gov.ua/handle/123456789/188414 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
We study asymptotics of the spectral measure of a randomly chosen partial automorphism of a rooted tree. To every partial automorphism x we assign its action matrix Ax. It is shown that the uniform distribution on eigenvalues of Ax converges weakly in probability to δ₀ as n → ∞, where δ₀ is the delta measure concentrated at 0. |
| format |
Article |
| author |
Kochubinska, E. |
| spellingShingle |
Kochubinska, E. Spectral properties of partial automorphisms of a binary rooted tree Algebra and Discrete Mathematics |
| author_facet |
Kochubinska, E. |
| author_sort |
Kochubinska, E. |
| title |
Spectral properties of partial automorphisms of a binary rooted tree |
| title_short |
Spectral properties of partial automorphisms of a binary rooted tree |
| title_full |
Spectral properties of partial automorphisms of a binary rooted tree |
| title_fullStr |
Spectral properties of partial automorphisms of a binary rooted tree |
| title_full_unstemmed |
Spectral properties of partial automorphisms of a binary rooted tree |
| title_sort |
spectral properties of partial automorphisms of a binary rooted tree |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2018 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/188414 |
| citation_txt |
Spectral properties of partial automorphisms of a binary rooted tree / E. Kochubinska // Algebra and Discrete Mathematics. — 2018. — Vol. 26, № 2. — С. 280–289. — Бібліогр.: 6 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT kochubinskae spectralpropertiesofpartialautomorphismsofabinaryrootedtree |
| first_indexed |
2025-07-16T10:26:52Z |
| last_indexed |
2025-07-16T10:26:52Z |
| _version_ |
1837798903861215232 |
| fulltext |
“adm-n4” — 2019/1/24 — 10:02 — page 280 — #130
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 26 (2018). Number 2, pp. 280–289
c© Journal “Algebra and Discrete Mathematics”
Spectral properties of partial automorphisms
of a binary rooted tree
Eugenia Kochubinska
Communicated by A. P. Petravchuk
Abstract. We study asymptotics of the spectral measure
of a randomly chosen partial automorphism of a rooted tree. To
every partial automorphism x we assign its action matrix Ax. It is
shown that the uniform distribution on eigenvalues of Ax converges
weakly in probability to δ0 as n → ∞, where δ0 is the delta measure
concentrated at 0.
Introduction
We consider a semigroup of partial automorphisms of a binary n-
level rooted tree. Throughout the paper by a partial automorphism we
mean root-preserving injective tree homomorphism defined on a connected
subtree. This semigroup was studied, in particular, in [4, 5].
We are interested in spectral properties of this semigroup. There is
a lot of paper dealing with spectrum of action matrices for the action
of finitely generated groups on a regular rooted tree. The exhaustive
research on spectra of fractal groups is provided in [1]. The eigenvalues
of random wreath product of symmetric group were studied by Evans
in [2]; he assigned equal probabilities to the eigenvalues of a randomly
chosen automorphism of a regular rooted tree, and considered the random
measure Θn on the unit circle C. He has shown that Θn converges weakly
2010 MSC: 20M18, 20M20,05C05.
Key words and phrases: partial automorphism, semigroup, eigenvalues, random
matrix, delta measure.
“adm-n4” — 2019/1/24 — 10:02 — page 281 — #131
E. Kochubinska 281
in probability to λ as n → ∞, where λ is the normalized Lebesgue measure
on the unit circle.
Let Bn = {vni | i = 1, . . . , 2n} be the set of vertices of the nth level of
the n-level binary rooted tree. To a randomly chosen partial automorphism
x, we assign the action matrix Ax =
(
1{x(vni )=vnj }
)2n
i,j=1
. Let
Ξn =
1
2n
2n
∑
k=1
δλk
be the uniform distribution on eigenvalues of Ax. We show that Ξn
converges weakly in probability to δ0 as n → ∞, where δ0 is the delta
measure concentrated at 0. This result can be generalized to a regular
rooted tree, however, this generalization is not straightforward and will
be studied elsewhere.
The remaining of the paper is organized as follows. Section 2 contains
basic facts on a partial wreath product of semigroup and its connection
with a semigroup of partial automorphisms of a regular rooted tree. The
main result is stated and proved in Section 3.
1. Preliminaries
For a set X = {1, 2} consider the set I2 of all partial bijections. List
all of them using standard tableax representation:
{(
1 2
1 2
)
,
(
1 2
2 1
)
,
(
1 2
1 ∅
)
,
(
1 2
∅ 2
)
,
(
1 2
2 ∅
)
,
(
1 2
∅ 1
)
,
(
1 2
∅ ∅
)}
.
This set forms an inverse semigroup under natural composition law, namely,
f ◦ g : dom(f)∩ f−1 dom(g) ∋ x 7→ g(f(x)) for f, g ∈ I2. Obviously, I2 is
a particular case of the well-known inverse symmetric semigroup. Detailed
description of it can be found in [3, Chapter 2].
Recall the definition of a partial wreath product of semigroups. Let S
be an arbitrary semigroup. For functions f : dom(f) → S, g : dom(g) → S
define the product fg as:
dom(fg) = dom(f) ∩ dom(g), (fg)(x) = f(x)g(x) for all x ∈ dom(fg).
For a ∈ I2, f : dom(f) → S, define fa as:
(fa)(x) = f(xa), dom(fa) = {x ∈ dom(a);xa ∈ dom(f)}.
“adm-n4” — 2019/1/24 — 10:02 — page 282 — #132
282 Spectral properties of partial automorphisms
Definition 1. The partial wreath square of the semigroup I2 is the set
{(f, a) | a ∈ I2, f : dom(a) → I2}
with composition defined by
(f, a) · (g, b) = (fga, ab)
Denote it by I2 ≀p I2.
The partial wreath square of I2 is a semigroup, moreover, it is an
inverse semigroup [6, Lemmas 2.22 and 4.6]. We may recursively define any
partial wreath power of the finite inverse symmetric semigroup. Denote
by Pn the nth partial wreath power of I2.
Definition 2. The partial wreath n-th power of semigroup I2 is defined
as a semigroup
Pn =
(
Pn−1
)
≀p I2 = {(f, a) | a ∈ I2, f : dom(a) → Pn−1}
with composition defined by
(f, a) · (g, b) = (fga, ab),
where Pn−1 is the partial wreath (n− 1)-th power of semigroup I2
Proposition 1. Let Nn be the number of elements in the semigroup Pn.
Then Nn = 22
n+1−1 − 1
Proof. We proceed by induction.
If n = 1, then 22
2−1 − 1 = 7. This is exactly the number of elements
in I2.
Assume that Nn−1 = 22
n−1 − 1. Then
Nn = |{(f, a) | a ∈ I2, f : dom(a) → Nn−1}|
=
∑
a∈I2
N
|dom(a)|
n−1 =
∑
a∈I2
(
22
n−1 − 1
)|dom(a)|
= 1 + 4 · (22
n−1 − 1) + 2 · (22
n−1 − 1)2
= 1 + 4 · 22
n−1 − 4 + 2 · 22
n+1−2 − 4 · 22
n−1 + 2 = 22
n+1
− 1.
Remark 1. Let T be an n-level binary rooted tree. We define a partial
automorphism of a tree T as an isomorphism x : Γ1 → Γ2 of subtrees
Γ1 and Γ2 of T containing a root. Denote dom(x) := Γ1, ran(x) := Γ2
domain and image of x respectively. Let PAutT be the set of all partial
automorphisms of T . Obviously, PAutT forms a semigroup under natural
composition law. It was proved in [4, Theorem 1] that the partial wreath
power Pn is isomorphic to PAutT .
“adm-n4” — 2019/1/24 — 10:02 — page 283 — #133
E. Kochubinska 283
2. Asymptotic behaviour of a spectral measure of a
binary rooted tree
We identify x ∈ Pn with a partial automorphism from PAutT . Recall,
that Bn denotes the set of vertices of the nth level of T . Clearly, |Bn| = 2n.
Let us enumerate the vertices of Bn by positive integers from 1 to 2n:
Bn = {vni | i = 1, . . . , 2n} .
To a randomly chosen transformation x ∈ Pn, we assign the matrix
Ax =
(
1{x(vni )=vnj }
)2n
i,j=1
.
In other words, (i, j)th entry of Ax is equal to 1, if a transformation x
maps vni to vnj , and 0, otherwise.
Remark 2. In an automorphism group of a tree such a matrix describes
completely the action of an automorphism. Unfortunately, for a semigroup
this is not the case.
Example 1. Consider the partial automorphism x ∈ P2, which acts in
the following way
v01
v11 v12
v21 v22 v23 v24
//oo
(dotted lines mean that these edges are not in domain of x).
Then the corresponding matrix for x is
Ax =
0 0 1 0
0 0 0 1
0 0 0 0
0 0 0 0
.
“adm-n4” — 2019/1/24 — 10:02 — page 284 — #134
284 Spectral properties of partial automorphisms
Note that if v12 were not in the dom(x) with action on other vertices
preserved, then the corresponding matrix would be the same.
Let χx(λ) be the characteristic polynomial of Ax and λ1, . . . , λ2n be
its roots respecting multiplicity. Denote
Ξn =
1
2n
2n
∑
k=1
δλk
the uniform distribution on eigenvalues of Ax.
Theorem 1. For any function f ∈ C(D), where D = {z ∈ C | |z| 6 1}
is a unit disc,
∫
D
f(x) Ξn(dx)
P
−→ f(0), n → ∞. (1)
In other words, Ξn converges weakly in probability to δ0 as n → ∞, where
δ0 is the delta-measure concentrated at 0.
Remark 3. Evans [2] has studied asymptotic behaviour of a spectral
measure of a randomly chosen element σ of n-fold wreath product of the
symmetric group Sd.
He considered the random measure Θn on the unit circle C, assigning
equal probabilities to the eigenvalues of σ.
Evans has shown that if f is a trigonometric polynomial, then
lim
n→∞
P
{∫
C
f(x)Θn(dx) 6=
∫
f(x)λ(dx)
}
= 0,
where λ is the normalized Lebesgue measure on the unit circle. Conse-
quently, Θn converges weakly in probability to λ as n → ∞.
In fact, Theorem 1 speaks about the number of non-zero roots of
characteristic polynomial χx(λ). Let us find an alternative description for
them. Denote
Sn(x) =
⋂
m>1
dom(xm) =
{
vnj | vnj ∈ dom(xm) for all m > 1
}
the vertices of the nth level, which “survive” under the action of x, and
define the ultimate rank of x by rkn(x) = |Sn(x)|. Let Rn denote the total
number of these vertices over all x ∈ Pn, that is
Rn =
∑
x∈Pn
rkn(x).
We call the number Rn the total ultimate rank.
“adm-n4” — 2019/1/24 — 10:02 — page 285 — #135
E. Kochubinska 285
Lemma 1. For x ∈ Pn the number of non-zero roots of χx with regard
for multiplicity is equal to the ultimate rank rkn(x) of x.
Proof. Let x ∈ Pn and Ax be its action matrix. Consider Ax as a matrix in
a standard basis. Let w be some basis vector. It follows from the definition
of Ax that there are two possibilities: if the vertex v corresponding to w
is in domain of x, then Ax sends w to another basis vector, otherwise, to
the zero vector. Since x is a partial bijection, applying Ax repeatedly, we
can either get the same vector or the zero vector; An
xw = 0 means that
v /∈ domxn. In the first case, the vector w corresponds to a non-zero root
of χx (some root of unity), and the vertex v contributes to the ultimate
rank. In the second case, the vector is a root vector for the zero eigenvalue,
so it corresponds to a zero root of Ax, while the corresponding vector does
not contribute to the ultimate rank.
Denote rankn(x) = | dom(x) ∩Bn| and define the total rank
R′
n =
∑
x∈Pn
rankn(x).
Remark 4. Clearly, for x = (f, a), where a ∈ I2, f : dom(a) → Pn−1,
rankn(x) =
∑
y∈dom(a)
rankn−1(f(y)) (2)
if dom(a) 6= ∅ and rankn(x) = 0 otherwise.
Lemma 2. Let R′
n be the total rank of the semigroup Pn. Then
R′
n = 4R′
n−1 + 4R′
n−1Nn−1.
Proof. Thanks to (2),
R′
n =
∑
x=(f,a)∈Pn
rankn(x) =
∑
x=(f,a)∈Pn
∑
y∈dom(a)
rankn−1(f(y))
=
∑
a∈I2
|dom(a)|=1
∑
f1∈Pn−1
rankn−1(f1)
+
∑
a∈I2
|dom(a)|=2
∑
f1,f2∈Pn−1
(rankn−1(f1) + rankn−1(f2))
= 4R′
n−1 + 2
∑
f1,f2∈Pn−1
(rankn−1(f1) + rankn−1(f2)) .
“adm-n4” — 2019/1/24 — 10:02 — page 286 — #136
286 Spectral properties of partial automorphisms
We have
∑
f1,f2∈Pn−1
rankn−1(f1) =
∑
f1∈Pn−1
∑
f2∈Pn−1
rank(f1)
=
∑
f1∈Pn−1
Nn−1 rank(f1) = Nn−1R
′
n−1.
Hence, by symmetry, R′
n = 4R′
n−1 + 4R′
n−1Nn−1.
Lemma 3. Let R′
n be the total rank of the semigroup Pn. Then
R′
n = 2n−1(1 +Nn) = 22
n+n−2.
Proof. We proceed by induction. A direct calculation gives
R′
1 = 8 = 1 +N1.
Assuming that
R′
n−1 = 22
n−1+n−3,
we have, thanks to Lemma 2 and Proposition 1,
R′
n = 4R′
n−1(1 +Nn−1) = 4 · 22
n−1+n−3 · 22
n−1−1 = 22
n+n−2,
as required.
Lemma 4. Let Rn be the total ultimate rank of the semigroup Pn. Then
Rn 6 3Rn−1 + 3Rn−1Nn−1.
Proof. Represent Rn as a sum
Rn =
∑
x=(f,a)∈Pn
rkn(x) =
∑
x=(f,a)∈Pn
|dom(a)|=1
rkn(x) +
∑
x=(f,a)∈Pn
|dom(a)|=2
rkn(x).
If rank(a) = 1, then we will be interested only in those a for which
a = (1) and a = (2), since otherwise the ultimate rank of x is 0. Therefore,
∑
x=(f,a)∈Pn
| dom(a)|=1
rkn(x) =
∑
a∈{(1),(2)}
∑
f1∈Pn−1
rkn−1(f1)
= 2
∑
f1∈Pn−1
rkn−1(f1) = 2Rn−1.
“adm-n4” — 2019/1/24 — 10:02 — page 287 — #137
E. Kochubinska 287
If rank(a) = 2, then
∑
x=(f,a)∈Pn
| dom(a)|=2
rkn(x) =
∑
x=(f,a)∈Pn
a=(1)(2)
rkn(x) +
∑
x=(f,a)∈Pn
a=(12)
rkn(x) =: S1 + S2.
Clearly, if x = (f, a) with a = (1)(2), then rkn(x) = rkn−1(f(1)) +
rkn−1(f(2)), whence
S1 =
∑
f1,f2∈Pn−1
(rkn−1(f1) + rkn−1(f2))
= 2
∑
f1,f2∈Pn−1
rkn−1(f1) = 2Rn−1Nn−1.
Further, if x = (f, a) with a = (12), then rkn(x) = 2 rkn−1(f(1)(f(2)).
So,
S2 = 2
∑
f1,f2∈Pn−1
rkn−1(f1f2).
Note that every element x ∈ Pn can be represented as a product
x = eσ, where e is an idempotent on dom(x) and σ is a permutation on
the set of the tree vertices. Then
∑
x2∈Pn−1
rkn−1(x1x2) =
∑
x2∈Pn−1
rkn−1(eσx2) =
∑
x2∈Pn−1
rkn−1(ex2).
The last equality is true since transformation x 7→ σx is bijective on Pn−1.
It follows from above that
S2 = 2
∑
f1,f2∈Pn−1
rkn−1(f1f2) = 2
∑
f1∈Pn−1
∑
f2∈Pn−1
rkn−1(iddom(f1) f2)
6 2
∑
f1∈Pn−1
∑
f2∈Pn−1
|dom(f1) ∩ Sn−1(f2)|
= 2
∑
f1∈Pn−1
∑
f2∈Pn−1
2n−1
∑
j=1
1{vn−1
j ∈dom(f1)}
· 1{vn−1
j ∈Sn−1(f2)}
= 2
2n−1
∑
j=1
∑
f1∈Pn−1
1{vn−1
j ∈dom(f1)}
·
∑
f2∈Pn−1
1{vn−1
j ∈Sn−1(f2)}
.
“adm-n4” — 2019/1/24 — 10:02 — page 288 — #138
288 Spectral properties of partial automorphisms
Thanks to symmetry, for each j, we have
∑
x∈Pn
1{vn−1
j ∈dom(x)} =
∑
x∈Pn
1{vn−1
1
∈dom(x)}.
Therefore,
1
2n
∑
x∈Pn
2n−1
∑
k=1
1{vn−1
k
∈dom(x)} =
1
2n−1
|dom(x)| .
Thus, we can write
S2 = 2
2n−1
∑
j=1
∑
f1∈Pn−1
1
2n−1
|dom(f1)|1{vn−1
j ∈Sn−1(f2)}
=
1
2n−1
∑
f1∈Pn
|dom(f1)|
2n
∑
j=1
1{vn−1
j ∈Sn−1(f2)}
= 2 ·
1
2n−1
∑
f1∈Pn−1
|dom(f1)| ·
∑
f2∈Pn−1
|Sn−1(f2)| .
Using that |Sn−1(f2)| = rkn−1(f2), |dom(f1)| = rank(f1), and applying
Lemma 3, we get
2
2n−1
Rn−1R
′
n−1 =
2Rn−1 · (1 +Nn−1)2
n−2
2n−1
=
2Rn−1(1 +Nn−1)
2
= (1 +Nn−1)Rn−1.
Therefore,
Rn 6 2Rn−1+2Rn−1Nn−1+(1+Nn−1)Rn−1 = 3Rn−1+3Rn−1Nn−1.
Lemma 5. Let pn =
Rn
2nNn
for n ∈ N. Then
pn 6
3
4
pn−1, n > 2.
Proof. Using Lemma 4, we get
pn =
Rn
2nNn
6
3Rn−1 + 3Rn−1Nn−1
2nNn
=
3Rn−1(1 +Nn−1)
2nNn
=
3Rn−1 · 2
2n−1
2n(22n+1−1 − 1)
=
3
2
·
Rn−1
2n−1(22n − 21−2n)
6
3
2
·
Rn−1
2n−1(22n − 2)
=
3
2
·
Rn−1
2n(22n−1 − 1)
=
3
4
·
Rn−1
2n−1Nn−1
=
3
4
· pn−1.
“adm-n4” — 2019/1/24 — 10:02 — page 289 — #139
E. Kochubinska 289
Proof of Theorem 1. Note that
∫
D
f(z)Ξn(dz) = 1
2n
∑2n
k=1 f(λk), where
λ1, . . . , λ2n are the roots of the characteristic polynomial χx(λ).
Then, thanks to Lemma 1,
∣
∣
∣
∣
∫
D
f(z)Ξn(dz)− f(0)
∣
∣
∣
∣
=
∣
∣
∣
∣
∫
D
(f(z)− f(0)) Ξ(dz)
∣
∣
∣
∣
6
1
2n
∑
k:λk 6=0
|(f(k)− f(0))| 6 2max
D
|f | ·
|k : λk 6= 0|
2n
= 2max
D
|f |
rkn(x)
2n
.
Therefore,
E
∣
∣
∣
∣
∫
D
f(z)Ξ(dz)− f(0)
∣
∣
∣
∣
6 2max |f | ·
∑
z∈Pn
rkn(x)
2nNn
= 2max |f | · pn,
where pn is defined in Lemma 5. By Lemma 5, pn 6
3
4 · pn−1 6 . . . 6
(34)
n−1p0, whence pn → 0, n → ∞.
Consequently, E
∣
∣
∫
D
f(z)Ξ(dz)− f(0)
∣
∣ → 0, n → ∞, whence the state-
ment follows.
Remark 5. We can see from the proof that the rate of convergence in
(1) is in some sense exponential.
References
[1] Bartholdi L., Grigorchuk R. On the Hecke type operators related to some fractal
groups, Proc. Steklov Inst. Math. 231, 2000, pp. 1-41.
[2] Evans S.N. Eigenvaluse of random wreath products, Electron. J. Probability. Vol.7,
No. 9, 2002, pp. 1-15.
[3] Ganyushkin O., Mazorchuk V. Classical Finite Transformation Semigroups. An
Introduction, Springer, 2008.
[4] Kochubinska E. Combinatorics of partial wreath power of finite inverse symmetric
semigroup ISd, Algebra discrete math., 2007, N.1, pp. 49-61.
[5] Kochubinska E.On cross-sections of partial wreath product of inverse semigroups,
Electron. Notes Discrete Math., Vol.28, 2007, pp. 379-386.
[6] Meldrum J.D.P. Wreath product of groups and semigroups, Pitman Monographs
and Surveys in Pure and Applied Mathematics, 74. Harlow: Longman Group Ltd.
1995.
Contact information
E. Kochubinska Taras Shevchenko National University of Kyiv,
Volodymyrska, 64, 01601, Kiev, Ukraine
E-Mail(s): eugenia@univ.kiev.ua
Received by the editors: 29.08.2017
and in final form 17.12.2017.
|