Hata and Yamaguti [1] have obtained the formula

Directed networks and self-similar systems

Katsushi Muramoto and Takeshi Sekiguchi

Abstract. The formula ^∂L_∂r^r

r=¹₂ = 2T in Hata and Yamaguti [1], where Lr is Salem’s singular function andT is the Takagi function, was generalized to the formula ^∂_∂r^kLk^r=k!Tr,k in Sekiguchi and Shiota [17] by using the measure theoretic method, whereTr,k is thek-th or- der Takagi function. In this paper we reconsider these functions from the viewpoint of de Rham’s functional equation, and by investigating such functional equation on a directed network we expand the above formula without the measure theoretic method.

1. Introduction

Hata and Yamaguti [1] have obtained the formula

r=¹₂

= 2T , which connects the Takagi function T with Salem’s singular function L

. The Takagi function takes the form T (x) =

P

n=0 1

2ⁿ

f (ψ

x) for x ∈ [0, 1], where f (x) = || 2x − 1 | − 1 | and ψ(x) = 2x( mod 1), and Salem’s singular function L

, which is called a “Lebesgue’s singular function”, is a unique continuous solution with L

(1) = 1 of the following functional equation:

L

(x) = rL

(ψ(x))1

(x)+ { r+(1 − r)L

(ψ(x)) } 1

(x) (x ∈ [0, 1]), (1) where r is a complex number with max {| r | , | 1 − r |} < 1. This formula has been extended up to the k-th derivative of L

in [17]. Namely, they took notice of that L

is the distribution of the binomial probability measure, and by using the measure theoretical technique they proved the formula

Key words and phrases. fractal, Takagi function, network, graph, de Rham’s func- tional equation.

1

∂^kLr

∂r^k

= k!T

, in which the higher-order Takagi function T

was defined by T

(x) =

X

2

X

r

(1 − r)

B

◦ ψ

(x)1

(x) (2) where

B

(x) =

 



L

◦ ψ(x)1

(x) + (1 − L

◦ ψ(x))1

(x) (k = 1), T

◦ψ(x)(1

(x) − 1

(x)) (k ≥ 2), s(n) is the sum of digits in the binary expansion of n, J

= [

,

[ for 0 ≤ j < 2

−2 and J

= [

, 1]. The higher-order Takagi function was used for the explicit representation of power sums of digital sums in [12].

Furthermore those results were extended for the digital sum problems on the different types of number system in [11], [3] and [2]. However it seems that the way to define the higher-order Takagi function is too technical, although their measure theoretic method is forceful.

In this paper we reconsider these functions from the viewpoint of some functional equation without the measure theoretic method, and investigate what causes the above definition of the higher-order Takagi function. We take notice of that the above functional equation (1) is a special case of de Rham’s functional equation in [18]. By differentiating the equation (1) formally with respect to r, we get the functional equation

∂Lr

∂r

(x) = { r

(ψ(x))+L

(ψ(x)) } 1

(x)

+ { (1 − r)

(ψ(x))+1 − L

(ψ(x)) } 1

(x) (x ∈ [0, 1]), (3) and the Takagi function appears in its solution for the case r =

. Fur- thermore, by setting that r =

"

r 1 0 r

#

and L

(x) =

"

L

(x)

(x) 0 L

(x)

# , we combine the above two functional equations (1) and (3) and then we get the following

L

(x) = r L

(ψ(x))1

(x) + { r+(e − r) L

(ψ(x)) } 1

(x) (x ∈ [0, 1]), (4)

where e is a unit matrix. The functional equation (4) is the same as (1)

except that those r and L

(x) are matrices, and so (4) is an extension of

(1). Moreover we reconsider (4) on Q

1

{ 0, 1 } instead of [0, 1], because [0, 1]

is considered to be Q

1

{ 0, 1 } by the dyadic expansion, and then each of ψ, J

and J

in (4) are replaced by φ, {0} × Q

1

{0, 1} and {1} × Q

1

{0, 1}, where φ is the shift on Q

1

{ 0, 1 } . As generalization of this functional equation, we define the system SRF(z) of functional equations on the di- rected network (G, m, τ ) and show its fundamental properties in Section 2.

This seems to be the first attempt to extending another aspect of Hata- Yamaguchi’s formula. For more information on the relation between T , L

and (G, m, τ ), refer to examples in Section 5. In Section 3, by introduc- ing the two kinds of transformations D

and U

, we show the existence and uniqueness of solutions of SRF(z), and we also give some expansion to its solutions. In Section 4 we investigate SRF(z) of the type like (4), and by applying the result of Section 2 to it we get a general form of (2) for SRF(z). In Section 5 we shall define the mappings Ψ

and Ψ

to translate the functional equations on Ω

to the ones on [0, 1], and rewrite Theorem 4.1 in this case. In Section 6 we give glossary of symbols used in this paper.

We use the following notations. Let N , Z , R and C be the sets of nat- ural numbers(including 0), integers, real numbers and complex numbers respectively. Set N

= N \ { 0 } . We denote the set of all mappings from a set X to a set Y by Map(X, Y ), the set of all continuous mappings from a set X to a set Y by C(X, Y ) if X and Y are topological spaces, the direct sum of a family of sets { B

: a ∈ A } with a parameter set A by

`

a∈A

B

= S

a∈A

{ a } × B

, the set of all mappings from A to S

a∈A

B

such that the image f

of a is in B

for each a in A by Γ( `

a∈A

B

), and the number of all elements of a set C by ♯C . Moreover we denote the set of d × d matrices with coefficients in C by M(d, C ), and the set of upper triangle matrices in M(d, C ) by ∆(d, C ) .

2. Functional equations on directed networks

We start introducing the directed network (G, m, τ ).

Definition 2.1. Let G be a non empty finite set, S

= ∅ and S

= {0, . . . , k−

1 } for k in N

. Suppose that m : G −→ N

and τ : G

−→ G are mappings, where G

= `

g∈G

S

. Then the triple (G, m, τ ) is called the directed

network. We also call an element of G a node, and an element (g, j) of G

a (communication) path of (G, m, τ ) with the start point g and the end point τ (g, j ).

In the following we suppose that (G, m, τ) be a directed network.

Definition 2.2. For each g in G and k in N , we denote by S

the set of words with length k, which is defined by

S

=

 

 



 

 

{ ϵ } (k = 0),

S

(k = 1),

{ ij : i ∈ S

, j = j

. . . j

∈ S

} (k ≥ 2), where ϵ is the empty word and ij means ij

. . . j

. We denote `

g∈G

S

by G

and also use the notation (h, j

) that means (g, j) in G

such that j = j

. . . j

in S

and h = (g, j

. . . j

) in G

. Next we define the mapping ˜ τ : S

n∈N

G

−→ G by

˜ τ (g) =

 

 



 

 

g if g = (g, ϵ) ∈ G

, τ (g, j) if g = (g, j) ∈ G

,

τ (˜ τ (h), j) if g = (h, j) ∈ G

, h ∈ G

, j ∈ S

(k ≥ 2).

The mapping τ ˜ is the extension of τ , and so we use the same notation τ instead of τ ˜ , and we call an element in G

a path with length k, be- cause (g, j

. . . j

) is a connection of paths (g, j

), (τ (g, j

), j

), . . . and (τ (g, j

. . . j

), j

) sequentially. We note that G

is identified with G and G

is G

.

Definition 2.3. Let Ω = Q

1

G

. We define the mapping φ : Ω −→ Ω as φ(ω) = (ω

, . . . , ω

, . . . ) for ω = (ω

, ω

, . . . , ω

, . . . ) in Ω, and, for each g in S

n∈N

G

, we define the mapping σ

: Ω −→ Ω by

σ

(ω) =

 

 

 

 

 

 

 



ω if g = (g, ϵ) ∈ G

,

(g, ω

, . . . , ω

, . . . ) if g = (g, j ) ∈ G

, σ

(σ

(ω)) if g = (h, j) ∈ G

,

h ∈ G

, j ∈ S

(k ≥ 2),

where ω = (ω

, . . . , ω

, . . . ) in Ω.

Definition 2.4. Let G

have the discrete topology and Ω have the product topology. We define Ω

for each g in G by

Ω

= n

((g

, j

), . . . , (g

, j

), . . . ) : g

= g, j

∈ S

and g

=τ (g

, j

), j

∈ S

for n ∈ N

o ,

and we denote σ

(Ω

) by I

for each g in S

n∈N

G

. Then it is clear that each I

is open, closed and compact, and that I

= Ω

= S

j∈S_g^∗n

I

for each g in G and n in N.

Definition 2.5. For each g in G and n in N

, the mappings π π π

: Ω

−→

S

and π

: Ω

−→ S

i∈Sg^∗(n−1)

S

are defined by π π π

(ω) = j

. . . j

and π

(ω) = j

, where ω = ((g

, j

), . . . , (g

, j

), . . . ) in Ω

. We use π π π

and π

as the mappings form Ω

to S

defined by π π π

(ω) =π

(ω) = ϵ.

We remark that π π π

(ω) = π

(ω) . . . π

(ω) and ω = σ

◦ φ

(ω) for ω in Ω

and n in N .

Definition 2.6. The mappings t, t

, t

: Ω −→ N ∪ {∞} are defined by t(ω) = min { k ∈ N : sup

m(g

) = 1 } ,

t

(ω) = min { k ∈ N : sup

j

= 0 } ,

t

(ω) = min { k ∈ N : sup

(m(g

) − j

) = 1 } , and the mapping s : N × Ω −→ N is defined by

s(n, ω) = ♯ { k ∈ N

: m(g

) > 1, k ≤ n } ,

where min ∅ = ∞ and ω = ((g

, j

), . . . , (g

, j

), . . . ) in Ω. Moreover we denote by 0

and m

− the elements in Ω

satisfying t

(ω) = 0 and t

(ω) = 0 respectively, and we use the following notations ω − and ω + for ω as follows:

ω − = σ

(m

− ) if 0 < t

(ω) < ∞ , ω + = σ

(0

) if 0 < t

(ω) < ∞,

where i=π π π

(ω)(π

(ω) − 1) and j =π π π

(ω)(π

(ω)+1).

We also use 0

− as an imaginary point, which is not in Ω

.

The next proposition is easily checked.

Proposition 2.1. The mappings s, t, t

, t

have the following properties:

1) t

≤ t, t

≤ t and t

∨ t

= t.

2) if n ≤ t(ω), ω ∈ Ω

, then s(n, ω) ≥ b

c .

Definition 2.7. Let the mapping z :G

−→ M(d, C ) satisfy P

k∈S_g^∗1

z

(k) =e for g in G, where e is the unit matrix and z

(k) is the image of (g, k) in G

. We define the system of de Rham functional equations with the weighted parameter z associated with (G, m, τ ), that is abbreviated to be “ SRF(z) on (G, m, τ) ”, by the following equations:

 



L

(m

− ) = e, L

(ω) = P

0≤k<j

z

(k) + z

(j) L

(φ(ω)) (ω ∈ I

, j ∈ S

)

(5) for g in G. We only deal with continuous solutions L

of (5). Strictly speak- ing, we denote a continuous solution by L

, which belongs to C (Ω

, M(d, C )) and which index z means its weighted parameter for each g in G.

In the subsequent, we assume that the mapping z : G

−→ M(d, C ) satis- fies P

k∈S_g^∗1

z

(k) =e for each g in G, unless otherwise stated.

Lemma 2.1. Let L

be a solution of SRF(z). Then we have L

(σ

(m

− )) = L

(σ

(0

) − ) P

j<k<m(τ(g,i))

z

(k) + L

(σ

(m

− )) P

0≤k≤j

z

(k) (6) for i in S

, j in S

, n in N and g in G, where we set L

(0

− ) =0.

Proof. We prove this lemma by the induction. Let g in G and j in S

. By substituting σ

(m

− ) for ω in (5), we have

L

(σ

(m

− )) = P

0≤k<j

z

(k) + z

(j) L

(φ(σ

(m

− )))

= P

0≤k≤j

z

(k)

= L

(0

− ) P

j<k<m(g)

z

(k)+ L

(m

− ) P

0≤k≤j

z

(k), which is (6) in the case n= 0. Next let h in S

, i in S

and j in S

. By using (5) again, we have the following three equations:

L

(σ

(m

− ))

= P

0≤k<h

z

(k) + z

(h) L

(σ

(m

− )) (7) z

(h) L

(σ

(m

− ))

= L

(σ

(m

− )) − P

0≤k<h

z

(k) (8)

z

(h) L

(σ

(0

) − )

= L

(σ

(0

) − ) − P

0≤k<h

z

(k), (9)

and, by the induction assumption, we have L

(σ

(m

−))

= L

(σ

(0

) − ) P

j<k<m(τ(g,hi))

z

(k) + L

(σ

(m

− )) P

0≤k≤j

z

(k). (10) Then we substitute (10), (9) and (8) in (7) sequentially, and we have

L

(σ

(m

− ))

= P

0≤k<h

z

(k)

+ z

(h){L

(σ

(0

)−) P

j<k<m(τ(g,hi))

z

(k) + L

(σ

(m

−)) P

0≤k≤j

z

(k)}

= P

0≤k<h

z

(k)

+ {L

(σ

(0

) − ) − P

0≤k<h

z

(k) } P

j<k<m(τ(g,hi))

z

(k) + {L

(σ

(m

− )) − P

0≤k<h

z

(k) } P

0≤k≤j

z

(k)

= L

(σ

(0

) − ) P

j<k<m(τ(g,hi))

z

(k) + L

(σ

(m

− )) P

0≤k≤j

z

(k).

Namely we get (6) for the next n.

The above Lemma 2.1 means that any solution of SRF(z) is determined only by the parameter z on the set { σ

(m

− ) : i ∈ S

, n ∈ N} , which is dense in Ω

, for each g in G. That implies the following proposition.

Proposition 2.2. The continuous solution L

of SRF(z) is unique, and

each L

belongs to C (Ω

, ∆(d, C )) for g in G if z :G

−→ ∆(d, C ).

Definition 2.8. For the mapping z :G

−→ M(d, C ) we define the mapping

˜ z : S

n∈N

G

−→ M(d, C ) by

˜ z(g) =

 

 

 

 

 

 

 



e if g = (g, ϵ) ∈ G

, z

(j) if g = (g, j ) ∈ G

,

˜

z(h)z

(j) if g = (h, j) ∈ G

, h ∈ G

, j ∈ S

(k ≥ 2).

The mapping ˜ z is the extension of z, and so we use the same notation z instead of ˜ z. We also use the notation z

(j) as z(g) if g = (g, j) for g in G and j in S

.

Lemma 2.2. Let L

be a solution of SRF(z). If ω in Ω

and t

(ω) < ∞ , then we have

L

(ω) − L

(ω − ) = z

(i) L

(0

) (11) for g in G, where i in S

and ω = σ

(0

).

Proof. If t

(ω) = 0 then the left-hand side of (11) equals z

(ϵ) L

(0

) because of ω = 0

and i =ϵ. If t

(ω) = 1 then there exists j in S

such that j ≥ 1 and ω =σ

(0

), and so ω − =σ

(m

− ). Hence

L

(ω) = P

0≤k<j

z

(k) + z

(j) L

(0

) and

L

(ω − ) = P

0≤k<j−1

z

(k) + z

(j − 1) L

(m

− ) by (5), and then the left-hand side of (11) equals z

(j) L

(0

).

Next suppose that t

(ω) = n+2 and n ∈ N, that is, ω = σ

(0

) where h ∈ S

, i ∈ S

and 0 < j ∈ S

. Then we have ω − = σ

(m

− ) and φ(ω) = σ

(0

). Moreover we have φ(ω − ) = σ

(m

− ) = φ(ω) − and t

(φ(ω)) = n+ 1.

Hence

L

(ω) − L

(ω − ) = z

(h) {L

(φ(ω)) − L

(φ(ω) − ) }

by (5). Therefore (11) is obtained.

3. The existence and some expansion formulas of solutions of functional equations systems

We start by defining transformations D

and U

.

Definition 3.1. For each n in N , we define the transformations D

and U

on Γ( `

g∈G

Map(Ω

, M(d, C ))), as follows:

(D

F )

(ω) = P

j∈S_g^∗n

{F

(σ

(m

− )) − F

(σ

(0

) − ) } 1

(ω), (U

F )

(ω) = P

j∈S_g^∗n

F

(φ

(ω))1

(ω), where F in Γ( `

g∈G

Map(Ω

, M(d, C))), ω in Ω

, and F

(0

−) = 0 by using the imaginary point 0

− .

Definition 3.2. We define the mapping s: G

× S

n∈N

G

−→ N by s((g, j); (h, i)) = ♯{k : (τ (h, i

. . . i

), i

) = (g, j), 1 ≤ k ≤ n}, where (g, j ) ∈ G

, i = i

. . . i

∈ S

and h ∈ G. (Do not confuse with s(n, ω) in Definition 2.6.)

Definition 3.3. We define ρ(z) and η(z) by ρ(z) = max

max

g

max

|(z

(j))

|, η(z) = max

max

h

max

| (z

(k))

| for z :G

−→ ∆(d, C ), and use the notation kFk by

kFk = max

g∈G

sup

ω∈Ω

kF (ω)k for F ∈ Γ( a

g∈G

Map(Ω

, M(d, C))).

We next show fundamental properties of D

and U

.

Proposition 3.1. 1) For n in N, D

and U

are M(d, C)-linear trans- formations on Γ( `

g∈G

Map(Ω

, M(d, C ))), that is, these transformations satisfy

D

(a F +b G ) = aD

( F )+bD

( G ), U

(a F +b G ) = aU

( F )+bU

( G ),

D

( F a+ G b) = D

( F )a+D

( G )b,

U

( F a+ G b) = U

( F )a+U

( G )b

for F and G in Γ( `

g∈G

Map(Ω

, M(d, C )) and a and b in M(d, C ), where (a F )

(ω) = a( F

(ω)) and ( F a)

(ω) = ( F

(ω))a for ω in Ω

and g in G.

2) If F is in Γ( `

g∈G

C(Ω

, M(d, C))) then both U

F and D

F are so.

3) For n, n

and n

in N , U

satisfies that U

( FG ) = (U

F )(U

G ) and U

U

F = U

F for F and G in Γ( `

g∈G

Map(Ω

, M(d, C ))) , where FG is defined by ( FG )

(ω) = F

(ω) G

(ω) for g in G and ω in Ω

.

4) Let L

be a solution of SRF(z). Then we have the followings:

(D

L

)

(ω) = P

j∈S_g^∗n

z

(j)1

(ω) (ω ∈ Ω

, g ∈ G, n ∈ N), (12) D

L

= (D

L

)(U

D

L

) (n

, n

∈ N ). (13) Proof. We directly get 1), 2) and 3) from Definition 3.1. Since L

is a solution of (5), (12) with n = 0, 1 and (13) with n

= n

= 0 are clear. By Definition 3.1, we have

(D

L

)

(ω) = P

i∈S_g^∗n

P

j∈S_τ^∗1_(g,i)

{L

(σ

(m

− ))

− L

(σ

(0

) − ) } 1

(ω), and by Lemma 2.1 we get

L

(σ

(m

−)) = L

(σ

(0

) −) P

j<k<m(τ(g,i))

z

(k) + L

(σ

(m

−)) P

0≤k≤j

z

(k) (14) and

L

(σ

(0

) − ) = L

(σ

(0

) − ) P

j≤k<m(τ(g,i))

z

(k) + L

(σ

(m

− )) P

0≤k<j

z

(k) (15) for i in S

, j in S

, n in N and g in G. Therefore we have

(D

L

)

(ω)

= P

i∈S^∗_gⁿ

P

j∈S^∗1_τ(g,i)

{L

(σ

(m

− )) − L

(σ

(0

) − ) }

× z

(j)1

(ω)

= P

i∈S^∗n_g

{L

(σ

(m

− )) − L

(σ

(0

) − ) }

× { P

j∈S^∗1_τ(g,i)

z

(j)1

(φ

(ω)) } 1

(ω)

= P

i∈S^∗_gⁿ

{L

(σ

(m

− )) − L

(σ

(0

) − ) }

× (D

L

)

(φ

(ω))1

(ω)

= (D

L

)

(ω)(U

D

L

)

(ω),

that is, we get (13) with n

= n and n

= 1. Next we shall prove (12) and (13) with the remaining n, n

and n

, by the induction as follows:

(D

L

)

(ω) = (D

L

)

(ω)(U

D

L

)

(ω)

= P

i∈S_g^∗n

z

(i)1

(ω) P

k∈S^∗_gⁿ

(D

L

)

(φ

(ω))1

(ω)

= P

i∈S_g^∗n

z

(i)(D

L

)

(φ

(ω))1

(ω)

= P

i∈S_g^∗n

z

(i) P

j∈S_τ(g,i)^∗1

z

(j)1

(φ

(ω))1

(ω)

= P

j∈S^∗g⁽ⁿ⁺¹⁾

z

(j)1

(ω),

D

L

= (D

L

)(U

D

L

)

= (D

L

)(U

D

L

)(U

U

D

L

)

= (D

L

)(U

((D

L

)(U

D

L

)))

= (D

L

)(U

D

L

) and

(D

L

)(U

D

L

) = (D

L

)(U

((D

L

)(U

D

L

)))

= (D

L

)(U

D

L

)(U

D

L

)

= (D

L

)(U

D

L

).

We must estimate the product of upper triangle matrices before describ- ing the main result in this section.

Lemma 3.1. Let w

∈ ∆(d, C ) (k = 1, . . . , n) and set

α = max

| (w

)

| and β = max

| (w

)

| , where (w

)

(1 ≤ i, j ≤ d) are components of the matrix w

. Then we have

k w

w

· · · w

k ≤ C(n, α, β, d),