Lobachevskii Journal of Mathematics

http://ljm.ksu.ru

Vol. 15, 2004, 35–45

\begin{matrix}c \\ ◯ \end{matrix} Bin Wu

Bin Wu

ALGEBRAIC PROPERTIES OF REFINABLE SETS

(submitted by Yi Zhang)

Abstract. In this paper we study the algebraic properties of finite refinable sets which was introduced for the fast solution of integral equations. Furthermore, the family of refinable sets is classified according to the algebraic characteristics. Some open problems are raised for the future study.

Key words. Algebraic property, refinable set.

1. Introduction

The concept of refinable set was initially introduced in [1], as a preparative step of the fast collocation methods for solving integral equations (see [2]). The analysis of fast collocation scheme is based on the special properties of multiscale basis functions and multiscale functionals, while the refinable sets are used for the construction of multiscale functionals. In [1], the refinable set is defined as follows.

Definition 1.1. Let (X, d) be a complete metric space and Φ := {ϕ_{e} : e ∈ ℤ_{μ}}, ℤ_{μ} := {0, 1, …, μ − 1} be a family of contractive mappings on X, where μ is a positive integer. For any subset A ⊂ X, define

Φ(A) := ⋃_{e∈ℤ_{μ}} ϕ_{e}(A).  (1.1)

We say that a subset T ⊂ X is refinable relative to the mappings Φ if T ⊂ Φ(T).

This definition of refinable set aims at the needs of applications, thus involves analytic concepts such as metric, contractive mapping. Utilizing these concepts, the topological properties of refinable sets were studied in [1]. In this paper, we attempt to focus us on the algebraic aspect of this concept. Before the detailed discussions, we would like to give some simple examples to get the readers familiar with this terminology. Let X be the real number field equipped with the standard one-dimensional Euclidean metric d, and Φ := {ϕ_{0}, ϕ_{1}} is defined by

ϕ_{0}(t) := \frac{t}{2}, ϕ_{1}(t) := \frac{t + 1}{2}, t ∈ X.

It is not difficult to verify that the following subsets are refinable relative to Φ:

G_{0} := \{\frac{1}{3}, \frac{2}{3}\} ,  G_{1} := \{\frac{1}{7}, \frac{2}{7}, \frac{4}{7}\} ,  G_{2} := \{\frac{1}{5}, \frac{2}{5}, \frac{3}{5}, \frac{4}{5}\} ,

G′_{0} := \{\frac{1}{6}, \frac{1}{3}, \frac{2}{3}\} , G′′_{0} := \{\frac{1}{3}, \frac{2}{3}, \frac{5}{6}\} .

The sets G_{0}, G_{1} and G_{2} are “independent”, while G′_{0} and G′′_{0} are associated with G_{0}. To observe the relations among G_{0}, G′_{0} and G′′_{0}, we notice

Φ(G_{0}) = \{\frac{1}{6}, \frac{1}{3}, \frac{2}{3}, \frac{5}{6}\} ,

and find that G′_{0} and G′′_{0} are both the subsets of Φ(G_{0}). The set G_{0} is simpler than G′_{0} and G′′_{0} to the extent that we can find a proper refinable subset of G′_{0} or G′′_{0} while any proper subset of G_{0} is no longer refinable. It is one of the elementary problems of this paper to find and characteristic the simplest refinable set.

In section 2 we introduce several terminologies in the context of refinable sets such as source, image, kernel, degree, circle, which help to describe the algebraic properties. For a refinable set T, a kernel of T is a subset V ⊂ T such that Φ(V) ⊃ T. Our first task is to characteristic the simplest refinable set, which have itself as the unique kernel. We prove that T is the simplest if and only if for any t ∈ T, |Φ(t) ∩ T | = 1. We then observe this kind of refinable set itself is a circle, and any element of it is a fixed point of some composite mapping of those in Φ. Based on the above observations, we divide the whole family of refinable sets into three classes, and define two operations on the family so that all refinable sets can be generated from the simplest sets, which is called the refinable sets of the first kind.

In section 3, we turn to consider the upper bound for the number of the first kind refinable sets, and our estimate shows that they form a countable family. We also impose extra conditions on the mapping family Φ to get an accurate counting of the number of the first kind refinable sets.

There are still quite a few interesting issues left to be open. Since we only discuss in this paper the properties of the finite refinable sets, it is natural to ask whether the infinite refinable sets behave analogously. Is the family of infinite refinable sets countable? It is also not clear whether the finite refinable sets of the third kind generate a countable family.

2. Algebraic Characteristic of Refinable Sets

Definition 1.1 of refinable set involves some analytic concepts. In order to focus us on the algebraic aspect, we weaken the conditions on X and Φ to give a more general definition.

Definition 2.1. Let X be a number field, Φ := {ϕ_{e} : X → X : e ∈ ℤ_{μ}} is a family of mappings defined on X. A subset T ⊂ X is said to be refinable relative to mappings Φ, if T ⊂ Φ(T). Alternatively, we call T a refinable set relative to Φ, or simply a refinable set.

Remark: This definition states the concept in a more general background, and emphasizes the ultimate characteristic of refinable set, that is, a refinable set should be contained in its image under the mappings Φ.

In this paper we only study finite refinable sets. Hence when T is claimed to be refinable, |T |, the number of elements of T, is a finite positive integer.

We derive from the definition of refinable set the following lemma, which is frequently used as the equivalent definition of refinable set.

Lemma 2.2. T ∈ R(Φ) if and only if T = Φ(T) ∩ T.

We introduce below some concepts for the further discussion of refinable sets.

Definition 2.3. For T ∈ R(Φ), we call t ∈ T a (refinable) source of T, if there exists t′ ∈ T and ϕ_{e} ∈ Φ such that t′ = ϕ_{e}(t). In this case we call t′ an image of t in T under the mapping ϕ_{e}. If a subset V ⊂ T satisfies Φ(V) ⊃ T, then V is called a (refinable) kernel of T. Since the kernel of T may not be unique, we denote the set of all kernels of T by Θ(T), and

N (T) := min{|V | : V ∈ Θ(T)}  (2.2)

is called the (refinable) index of T.

It is easy to see that T ∈ Θ(T), hence Θ(T) is always nonempty, 0 < N (T) ≤ |T |, and N (T) = |T | if and only if Θ(T) = {T } is a single element set. When 0 < N (T) < |T |, we can not hold in hand the uniqueness of kernel V satisfying |V | = N (T). A necessary condition of this kind of kernel is easy to conclude, which is summarized in the following lemma. We remark that it is not a sufficient condition.

Lemma 2.4. Let T ∈ R(Φ), V ∈ Θ(T), |V | = N (T). Then any element of V is a source of T.

The proof of the following lemma is also trivial.

Lemma 2.5. Let T ∈ R(Φ). If G ∈ Θ(T), then (i) G ∈ R(Φ), hence Θ(T) ⊂ R(Φ); (ii) Any subset V satisfying G ⊂ V ⊂ T is in Θ(T), thus V ∈ R(Φ).

Similar to Lemma 2.2, we have V ∈ Θ(T) if and only if T = Φ(V)∩T.

Definition 2.6. Let T ∈ R(Φ), and v ∈ T is a source of T. We call |Φ(v)∩T | the degree of v. A source with degree 1 is called a single source, otherwise a multiple source.

The following theorem characterizes the refinable set T with the property N (T) = |T | through refinable sources.

Theorem 2.7. Let T ∈ R(Φ). Then N (T) = |T | if and only if each element of T is a single source of T. In this case, different elements of T have different images in T.

Proof. We first prove the necessity. Since N (T) = |T |, T is the unique kernel of itself. By Lemma 2.4, each element of T is a source. Assume that t_{0} ∈ T is a multiple source, i.e., |Φ(t_{0}) ∩ T | > 1. List the elements of T as follows,

T = {t_{0}, t_{1}, …, t_{n−1}},

where n = |T |, and for k ∈ ℤ_{n}, we denote T_{k} := {t_{i} : i ∈ ℤ_{k}}, T′_{k} := Φ(T_{k}) ∩ T. We prove by induction that

|T′_{i}| > i, i ∈ ℤ_{n} \ {0}.  (2.3)

The inequality holds for i = 1 since t_{0} is a multiple source. Assume that it also holds for i = k, and consider the case of i = k + 1. If

[Φ(t_{k}) ∩ T] ⊂ T_{k},

then

T = Φ(T) ∩ T = Φ(T \ {t_{k}}) ∩ T,

thus T \{t_{k}} ∈ Θ(T), which contradicts with the assumption. Therefore,

[Φ(t_{k}) ∩ T] \ T′_{k} ≠ ∅.

Since

T′_{k+1} = T′_{k} ⋃[(Φ(t_{k}) ∩ T) \ T′_{k}],

where

T′_{k} ⋂[(Φ(t_{k}) ∩ T) \ T′_{k}] = ∅,

we have

|T′_{k+1}| = |T′_{k}| + |[Φ(t_{k}) ∩ T] \ T′_{k}| > k + 1.

hence (2.3) is proven. Put i = n − 1, we obtain |Φ(T_{n−1}) ∩ T | > n − 1, i.e.,

Φ(T_{n−1}) ∩ T = T.

This implies T_{n−1} ∈ Θ(T), contradicting with the assumption. Hence t_{0} is a single source and the necessity is proven.

We now prove the sufficiency. Suppose that each element t ∈ T is a single source of T, and there is a kernel V ∈ Θ(T), |V | ≤ n − 1. Since any element v ∈ V is a single source of T, there holds

|Φ(V) ∩ T | ≤ n − 1,

which contradicts with Φ(V) ∩ T = T, hence N (T) = |T |.

If each element of T is a single source, then for any V ⊂ T, we have |Φ(V) ∩ T | ≤ |V |, and the equality holds if and only if different elements of V have different images in T. On the other hand, T ∈ R(Φ) implies |Φ(T)∩T | = |T |. Therefore, different elements of T have different images in T. □

Definition 2.8. Let T ∈ R(Φ), V := {v_{i} : i ∈ ℤ_{m}} ⊂ T, in which the v_{i}’s are distinct. If there exists e := [e_{i} : i ∈ ℤ_{m}] ∈ ℤ_{μ}^{m} such that for any i ∈ ℤ_{m}, v_{i+1} = ϕ_{e_{i}}(v_{i}), in which we denote v_{m} := v_{0}, then V is called a circle in T.

The concept of circle is elementary in the discussion of refinable sets, because the circle itself is refinable, and we have

Lemma 2.9. If T ∈ R(Φ), then T contains a circle.

Proof. Pick t_{0} ∈ T. Since T ⊂ Φ(T), we have t_{0} ∈ Φ(T), i.e., there exists t_{1} ∈ T and ϕ_{e_{1}} ∈ Φ such that t_{0} = ϕ_{e_{1}}(t_{1}). Similarly, we can find t_{2} ∈ T, ϕ_{e_{2}} ∈ Φ satisfying t_{1} = ϕ_{e_{2}}(t_{2}). Continuing this process will create a sequence t_{0}, t_{1}, t_{2}, . . .. Denote k := |T |, then there are two identical elements in the first k + 1 items of the sequence. We denote these two elements by t_{i} and t_{j}, where i < j, and require the elements of {t_{i}, t_{i+1}, …, t_{j−1}} are distinct. Thus V := {t_{i}, t_{i+1}, …, t_{j−1}} is a circle in T. □

For two circles V_{1} and V_{2} in T, we call V_{1} and V_{2} disjoint, if V_{1}∩Φ(V_{2}) = ∅ and V_{2}∩Φ(V_{1}) = ∅. The following proposition uses circle to characterize the refinable sets with N (T) = |T |.

Proposition 2.10. Let T ∈ R(Φ), and N (T) = |T |. Then any element of T is contained in some circle, i.e., for any v ∈ T, there is a circle V ⊂ T, such that v ∈ V. Moreover, the circles in T are disjoint.

Proof. Since N (T) = |T |, each element of T is a single source. Given v_{0} ∈ T, we can obtain in similar way to the proof of Lemma 2.9 a sequence v_{0}, v_{1}, …, v_{k}, where k := |T |. Furthermore, there is l ∈ ℤ_{k+1} \ {0} such that v_{l} = v_{0}. In fact, by Lemma 2.9, there exist i, j ∈ ℤ_{k+1}, i < j, such that v_{i} = v_{j}. If i = 0, that is just what we want. If i ≠ 0, noting that v_{i−1} ∈ Φ(v_{i}) ∩ T, v_{j−1} ∈ Φ(v_{j}) ∩ T, and v_{i} = v_{j} are both single sources of T, we conclude v_{i−1} = v_{j−1}. Continuing this process, we finally obtain v_{0} = v_{j−i}. Let m be the smallest integer such that v_{0} = v_{m}, then v_{0}, v_{1}, …, v_{m−1} are distinct. This is because if i, j ∈ ℤ_{m}, i < j such that v_{i} = v_{j}, then i > 0 by the definition of m. Then we have v_{0} = v_{j−i}, but j − i < m, which contradicts with the definition of m. Hence V := {v_{j} : j ∈ ℤ_{m}} is a circle in T.

We now prove the uniqueness of the circle containing v. Assume that there are two circles in T, V := {v_{0}, v_{1}, …, v_{k−1}} and V′ := {v_{0}, v′_{1}, …, v′_{p−1}}, in which v_{i+1} = ϕ_{e_{i}}(v_{i}), i ∈ ℤ_{k}, v′_{i+1} = ϕ_{e′_{i}}(v′_{i}), i ∈ ℤ_{p}, v_{0} = v′_{0} = v_{k} = v′_{p}. Since v_{1} and v′_{1} are both images of v_{0} in T, but v_{0} is a single source of T, we have v_{1} = v′_{1}. Similarly we conclude v_{i} = v′_{i}, i ∈ ℤ_{q}, q := min{k, p}. Since V ≠ V′, k ≠ p. Without loss of generality, we assume k < p, then v′_{k} and v_{0} are both images of v_{k−1}. But v_{k−1} is a single source, hence v_{0} = v′_{k}, which is a contradiction with the assumption. Thus the circle containing v_{0} is unique.

We have concluded that for any two circles V_{1} and V_{2} in T, there holds V_{1} ∩ V_{2} = ∅. Since any element of T is a single source, we have V_{2} = Φ(V_{2}) ∩ T, thus V_{1} ∩ Φ(V_{2}) = ∅. Similarly V_{2} ∩ Φ(V_{1}) = ∅. □

We conclude from the proposition above that a refinable set T satisfying N (T) = |T | has simple structure.

Theorem 2.11. Let T ∈ R(Φ), N (T) = |T |. Then there is a positive integer n such that

T = ⋃_{i∈ℤ_{n}} T_{i},

where T_{i}, i ∈ ℤ_{n} are disjoint circles in T.

Proof. According to Proposition 2.10, for any element t ∈ T, we can find unique circle in T, denoted by V_{t}, containing t. Thus

T = ⋃_{t∈T} V_{t}.

There may be identical circles in the above equality. We throw away the repeated circles to get

T = ⋃_{t∈U} V_{t},

where U ⊂ T, so that any two circles emerging in the above equality are not identical. Thus the circles are disjoint according to Proposition 2.10. □

Theorem 2.12. Let T ∈ R(Φ), then the following four conclusions are equivalent.

(i) Θ(T) = {T }, or Θ(T) is a single element set. (ii) N (T) = |T |. (iii) Any element of T is a single source. (iv) T can be represented as union of disjoint circles.

Proof. The equivalence of (i) and (ii) is obvious. We are to prove (iii) ⇒ (ii) ⇒ (iv) ⇒ (iii). By Theorem 2.7, (iii) ⇒(ii); According to Theorem 2.11, (ii)⇒(iv); it is left to prove (iv)⇒(iii). Since any element of T is in some circle, it is a source of T. On the other hand, if v ∈ T is a multiple source, we assume v is in circle V, then v has an image v′ ∉ V. But v′ should be in another circle V′, which contradicts with the disjoint assumption on V and V′. □

We now define two operations, which are based on the following fact.

Lemma 2.13. Let T, T′ ∈ R(Φ), then (i) T ∪ T′ ∈ R(Φ). (ii) For any v ∈ Φ(T) \ T, T ∪ {v} ∈ R(Φ).

Definition 2.14. Let T, T′ ∈ R(Φ), v ∈ Φ(T) \ T, {v} ∉ R(Φ), then we call T ∪ T′ union of the first kind, T ∪ {v} union of the second kind.

The proof of the following lemma is easy.

Lemma 2.15. Let T ∈ R(Φ), v ∉ T, {v} ∉ R(Φ), T ∪ {v} ∈ R(Φ), then v ∈ Φ(T) \ T.

Definition 2.16. Let T ∈ R(Φ). If T itself is a circle, then we call T a refinable set of the first kind; if T is the union of refinable sets of the first kind, then T is called a refinable set of the second kind; in other cases T is called a refinable set of the third kind.

Proposition 2.17. If Φ contains only one mapping, T ∈ R(Φ), then N (T) = |T |, thus T is of the first or second kind.

Theorem 2.18. Any refinable set of the second kind is the union of the first kind of refinable sets of the first kind; any refinable set of the third kind can be obtained by finite many unions of the second kind from a refinable set of the second kind.

Since the refinable sets of the first kind can generate the whole family R(Φ), it is important to characterize these sets. For e := (e_{0}, e_{1}, …, e_{ℓ−1}) ∈ ℤ_{μ}^{ℓ}, we define composite mapping ϕ_{e} := ϕ_{e_{0}} ∘ ϕ_{e_{1}} ∘ ⋯ ∘ ϕ_{e_{ℓ−1}}.

Theorem 2.19. Let T ∈ R(Φ) be a refinable set of the first kind, then for any t ∈ T, there exists e ∈ ℤ_{μ}^{k} such that t is a fixed point of ϕ_{e}, in which k := |T |.

Proof. According to the definition, we can write T as T := {t_{0}, t_{1}, …, t_{k−1}}, where t_{i+1} = ϕ_{e_{i}}(t_{i}), ϕ_{e_{i}} ∈ Φ, i ∈ ℤ_{k}, t_{k} = t_{0}. Let e := (e_{k−1}, e_{k−2}, …, e_{0}), then t_{0} = ϕ_{e}(t_{0}), i.e., t_{0} is the fixed point of ϕ_{e}. For t_{1}, Φ_{e′}(t_{1}) = t_{1}, where e′ := (e_{0}, e_{k−1}, …, e_{1}). In similar way we can prove that other elements are all fixed points. □

3. Refinable Sets of the First Kind

In this section we are focused on counting the number of the refinable sets of the first kind in R(Φ). Generally R(Φ) is an infinite set, so is the collection of the refinable sets of the first kind. What we are concerned about is the number of refinable sets of the first kind with a given cardinality. Denote by R_{I}^{r}(Φ) the refinable sets of the first kind in R(Φ) with cardinality r, and let ⌈x⌉ denote the largest integer not more than x.

We first make a partition of ℤ_{μ}^{r}. Define transformation w : ℤ_{μ}^{r} → ℤ_{μ}^{r} as follows: for e := (e_{0}, e_{1}, …, e_{r−1}) ∈ ℤ_{μ}^{r},

w(e) = (e_{r−1}, e_{0}, e_{1}, …, e_{r−2}) ∈ ℤ_{μ}^{r}.

We call w the right translation with screw on ℤ_{μ}^{r}. It is easy to see

w^{k}(e) = (e_{r−k}, …, e_{r−1}, e_{0}, …, e_{r−k−1}),

and

w^{r}(e) = e, w^{r+k}(e) = w^{k}(e).

For e ∈ ℤ_{μ}^{r}, define

Ξ(e) := {w^{k}(e) : k ∈ ℕ_{0}},

where we indicate w^{0}(e) = e. By the property of w, Ξ(e) is a finite set, and |Ξ(e)| ≤ r. If |Ξ(e)| = m, then we can write Ξ(e) equivalently as Ξ(e) = {w^{k}(e) : k ∈ ℤ_{m}}. For e, e′ ∈ ℤ_{μ}^{r}, either Ξ(e) = Ξ(e′), or Ξ(e)∩Ξ(e′) = ∅. Hence Ξ(ℤ_{μ}^{r}) := {Ξ(e) : e ∈ ℤ_{μ}^{r}} is a partition of ℤ_{μ}^{r}. For a positive integer k ≤ r, define Ξ_{k}(ℤ_{μ}^{r}) := {Ξ(e) ∈ Ξ(ℤ_{μ}^{r}) : |Ξ(e)| = k}. The following lemma is a direct corollary of Theorem 2.19.

Lemma 3.1. Let T ∈ R_{I}^{r}(Φ), t_{0} ∈ T, e ∈ ℤ_{μ}^{r}, ϕ_{e}(t_{0}) = t_{0}. Then for any t ∈ T, there exists e′ ∈ Ξ(e), such that ϕ_{e′}(t) = t.

Lemma 3.2. If Ξ_{k}(ℤ_{μ}^{r}) ≠ ∅, then k|r.

Proof. Pick Ξ(e) ∈ Ξ_{k}(ℤ_{μ}^{r}), where e := (e_{0}, e_{1}, …, e_{r−1}), then Ξ(e) = {e, w(e), …, w^{k−1}(e)}, and w^{k}(e) = e. According to the definition of w,

e_{ℓ} = e_{ℓ+k},  ℓ ∈ ℤ_{r},  (3.4)

where for ℓ ≥ r we let e_{ℓ} = e_{ℓ−r}. Divide r by k to obtain r = kp + q, q ∈ ℤ_{p}. If k is not a factor of r, then q ≠ 0. By (3.4), e_{kp} = e_{k(p+1)} = e_{k−q}. But e_{0} = e_{kp}, thus e_{0} = e_{k−q}. Similarly we have e_{ℓ} = e_{ℓ+k−q}, ℓ ∈ ℤ_{r}, or w^{k−q}(e) = e, hence |Ξ(e)| ≤ k − q < k, which contradicts with the assumptions. Therefore q = 0, and k|r. □

In the case of k|r, we can define a correspondence Ω_{k} : R_{I}^{k}(Φ) → Ξ_{k}(ℤ_{μ}^{r}) as follows: for V ∈ R_{I}^{k}(Φ), we arbitrarily pick v ∈ V, then by Theorem 2.19, there exists e ∈ ℤ_{μ}^{k} such that ϕ_{e}(v) = v. Since k|r, we can concatenate \frac{r}{k} e’s to form ẽ ∈ ℤ_{μ}^{r}. Then we identify Ξ(ẽ) ∈ Ω_{k}(V). Note that such Ξ(ẽ) may not unique. We still need to show Ξ(ẽ) ∈ Ξ_{k}(ℤ_{μ}^{r}), which holds if |Ξ(ẽ)| = k. Denote s := |Ξ(e)|, then V = {v′ : v′ = ϕ_{e}(v), e ∈ Ξ(e)}. Thus s ≥ k. On the other hand |Ξ(e)| ≤ k. Hence |Ξ(ẽ)| = |Ξ(e)| = k, so Ξ(ẽ) ∈ Ξ_{k}(ℤ_{μ}^{r}).

Theorem 3.3. Let k|r, then for V, V′ ∈ R_{I}^{k}(Φ), V ≠ V′, there holds Ω_{k}(V) ∩ Ω_{k}(V′) = ∅.

Proof. Since V ≠ V′, |V | = |V′|, there is v ∈ V \ V′ and v′ ∈ V′ \ V. Suppose v and v′ are the fixed points of ϕ_{e} and ϕ_{e′}, respectively, e, e′ ∈ ℤ_{μ}^{k}, then e ∉ Ξ(e′), e′ ∉ Ξ(e). Concatenate \frac{r}{k} e’s and e′’s to obtain ẽ and ẽ′ respectively, then ẽ ∉ Ξ(ẽ′), ẽ′ ∉ Ξ(ẽ). Hence Ξ(ẽ) ∩ Ξ(ẽ′) = ∅. □

Theorem 3.4. For any positive integer r, there holds

|R_{I}^{r}(Φ)| ≤ ⌈\frac{μ^{r}}{r} ⌉ .  (3.5)

Proof. It follows from Theorem 3.3 that

|R_{I}^{r}(ℤ_{μ}^{r})| ≤ |Ξ_{r}(ℤ_{μ}^{r})|.

On the other hand,

|Ξ_{r}(ℤ_{μ}^{r})| · r ≤ |ℤ_{μ}^{r}| = μ^{r}.

Then the theorem is proved. □

Corollary 3.5. The family of the refinable sets of the first kind is countable. Moreover, the refinable sets of the second kind also form a countable family.

The above theorem only provides a rough upper bound of |R_{I}^{r}(Φ)|. We can improve the estimate if stronger condition is imposed on Φ. For this purpose, we set the following hypothesis.

Hypothesis Λ: There exists a positive integer m, such that for any r < m, if e_{1}, e_{2} ∈ ℤ_{μ}^{r}, e_{1} ≠ e_{2}, then ϕ_{e_{1}} and ϕ_{e_{2}} have unique fixed points t_{1} and t_{2}, and t_{1} ≠ t_{2}.

This hypothesis is fulfilled in many important practical cases, for example, Φ is a family of contractive mappings, and for e, e′ ∈ ℤ_{μ}^{r}, e ≠ e′, there holds int(ϕ_{e}) ∩ int(ϕ_{e′}) = ∅.

Theorem 3.6. Assume that Φ satisfies hypothesis Λ. For r ∈ ℤ_{m} \ {0}, we denote P (r) := |R_{I}^{r}(Φ)|, then

P (r) = \frac{μ^{r} − ∑_{k∈φ(r)} k · P (k)}{r},  (3.6)

where φ(r) = {p : p ∈ ℤ_{r} \ {0}, p|r}.

Proof. We are to prove that for k|r, Ω_{k} is a bijection. Under the conditions of the theorem, for any V ∈ R_{I}^{k}(Φ), v ∈ V, the e ∈ ℤ_{μ}^{k} such that ϕ_{e}(v) = v is unique, hence Ω_{k} is a mapping. We then conclude from Theorem 3.3 that Ω_{k} is injective. On the other hand, for any Ξ(e) ∈ Ξ_{k}(ℤ_{μ}^{r}), ϕ_{e} has unique fixed point v_{0}. Then for m = 1, 2, …, k − 1, we find the unique fixed points v_{m} of ϕ_{w^{m}(e)}, respectively. Thus V := {v_{i} : i ∈ ℤ_{m}} is a refinable set of the first kind, and |V | = k. Therefore, Ω_{k} is surjective.

Given e ∈ ℤ_{μ}^{r}, we have |Ξ(e)| ≤ r, hence

Ξ(ℤ_{μ}^{r}) = ⋃_{k=1}^{r} Ξ_{k}(ℤ_{μ}^{r}).

By Lemma 3.2,

Ξ(ℤ_{μ}^{r}) = ⋃_{k∈φ(r)∪{r}} Ξ_{k}(ℤ_{μ}^{r}).

Given e ∈ ℤ_{μ}^{r}, |Ξ(e)| is uniquely determined, hence the subsets Ξ_{k}(ℤ_{μ}^{r}) of Ξ(ℤ_{μ}^{r}) are disjoint. By counting the number of vectors of ℤ_{μ}^{r} in the subsets Ξ_{k}(ℤ_{μ}^{r}), we conclude that

μ^{r} = ∑_{k∈φ(r)∪{r}} k · |Ξ_{k}(ℤ_{μ}^{r})|.

Since Ω_{k} is bijective, P (k) = |Ξ_{k}(ℤ_{μ}^{r})|, hence

P (r) = \frac{μ^{r} − ∑_{k∈φ(r)} k · P (k)}{r}.

□

Corollary 3.7. Suppose that Φ satisfies hypothesis Λ, then for a prime number r ∈ ℤ_{m} \ {0}, there holds

P (r) = \frac{μ^{r} − μ}{r}.  (3.7)

4. Open Problems

In this paper our discussions are restricted to finite refinable sets. It is left to study the algebraic properties of infinite refinable sets. The cardinality of the family of the third kind finite refinable sets is also not clear.

Another interesting issue is the relation between the number of the refinable sets and the properties of X and Φ. That is, if we impose more hypotheses on X and Φ, what will happen to the number of the refinable sets?

References

[1] Z. Chen, C. A. Micchelli, and Y. Xu, A construction of interpolating wavelets on invariant sets, Comp. Math. 68 (1999), 1560-1587.

[2] Z. Chen, C. A. Micchelli, and Y. Xu, Fast collocation methods for second kind integral equations, SIAM J. Numer. Anal., 40 (2002), 344-375.

[3] J. E. Hutchinson, Fractals and self similarity, Indiana Univ. Math. J., 30

(1981), 713-747.

E-mail address: wubin95@yahoo.com