数理解析研究所講究録1032 巻 1998 年 129-141

129

On the discrepancy of the -adic van der Corput sequence$\beta$Syoiti NINOMIYA (二宮祥–)
emil:$\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{o}\dot{\mathrm{m}}\mathrm{y}\mathrm{a}\mathrm{Q}\mathrm{t}\mathrm{r}1.\mathrm{m}.\mathrm{c}0\cdot \mathrm{j}_{\mathrm{P}}$IBM Research, Tokyo Research Laboratory

1623-14 Shimotsuruma, Yamato-shi,$\mathrm{K}\mathrm{a}\mathrm{n}\mathrm{a}\mathrm{g}\mathrm{a}\mathrm{w}\mathrm{a}\cdot \mathrm{k}\mathrm{e}\mathrm{n}u2$

Japan

概要

The -adic van der Corput sequence is constructed. When satisfies some conditions, the order
or $O((1_{\mathfrak{B}}M)^{2}/M)$.
of discrepancy of the sequenoe
sequence, numerical integraKeywords: -dic transformation, ergodiction, quasi-Monte Carlo method.
Mathematics Subject Classffication Numbers (1991): llK36, llK38, llK48.
$\beta$$\beta$$\mathrm{b}\alpha \mathrm{n}\mathrm{m}\mathrm{e}O(\log M/M)$$\beta$1$\mathrm{t}\mathrm{h}\infty \mathrm{r}\mathrm{y},$$\mathrm{l}\mathrm{o}\mathrm{W}A\mathrm{i}\mathrm{s}\mathrm{C}\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{m}\mathrm{c}\mathrm{y}$Introduction

sequences and their discrepancy play essential roles in quasi-Monte
It is well known thatsequenoesby using the -adic
Carlo methods [6]. The author constructed a new claae of
becomestransformation $[9][11]$ . Here, is a real number greater than 1; when is an integer greater than 2,
can be regarded as a generalization
the classical van der Corput sequence in base . Therefore, the classalso contains a new construction by Barat and Grabner [1] [7]. Theof the van der Corput sequence.
is that we can consider the van der Corput sequence to be a Kakutaniofprinciple of theand Hellekalek [4] also considered the van der Corput sequence from this point
adding machine [10].
of view. In [7], it is shown that when satisfies the following two conditions:$1\mathrm{o}\mathrm{W}A\mathrm{i}\mathrm{S}\mathrm{c}\mathrm{r}\mathrm{e}_{\mathrm{P}^{\mathrm{a}\mathrm{n}\mathrm{c}}}\mathrm{y}$$\mathrm{l}\mathrm{o}\mathrm{w}\prec \mathrm{l}\mathrm{i}\mathrm{S}\mathrm{c}\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{y}$$N_{\beta}[7]$$\beta$$\beta$$\beta$$\beta$$N_{\beta}$$N_{\beta}$$N_{\beta}$$\dot{\mathrm{c}}\mathrm{o}\mathrm{n}\mathrm{S}\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{C}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$$N_{\beta}$$\mathrm{P}\mathrm{a}\mathrm{g}^{\backslash }\mathrm{a}\mathrm{e}[8]$$\beta$.

$\bullet$Mdrkov condition:$\beta$is simple, that is to say, for this , the -adic transfomation becomes Markov,$\beta$Pisot-Vijayaraghavan condition: All oonjugates of$\{z\in \mathrm{C}||z|<1\}$ ,$\beta$$\beta$with respect to its characteristic equation belong todecreases in the fastest order $O(N^{-1}\log N)$ . In this paper, we consider the case in which
the discrepancy offrom Ito and Takahashi [5]. It is shown thatis not necessarily Markov. We introduce the function
when satisfies the following condition:$N_{\beta}$$\phi_{\beta}(z)$$\beta$.

$\beta$All zeroes of$1-\emptyset\rho(z)$except for $z=1$ belong to $\{z\in \mathrm{C}||z|>\beta\}$ ,which is a generalization of the above Pisot-Vijayaraghavan condition, the discrepancy oforder $O(N^{-1}(\log N)^{2})$ .

2$N_{\beta}$

decreasae in the

Low-discrepancy sequenceFirst, we recall the notions of a uniformly distributed sequence and the discrepancy of points [6]. A sequencein the -dimensional umit cube $I^{s}= \prod_{i=1}^{s}[0,1)$ is said to be uniformly distributed in when$x_{1},x_{2},$$\ldots$$I^{s}$$s$$\lim_{Narrow\infty}\frac{1}{N}\sum_{n=1}CNj(Xn)=\lambda s\mathrm{t}J)$130holds for all subintervals
Lebesgue measure. If$J\subset I^{s}$$x_{1},x_{2},$, whereis the characteristic function of andis a uniformly distributed sequence, the formula$J$$c_{J}$$\lambda_{l}$is the sdimensional$\ldots\in I^{\delta}$(2.1)$\lim_{Narrow\infty}\frac{1}{N}\sum_{\hslash}N=1f\mathrm{t}x_{n})=\int_{I}.f(X)dx$

holds for any Riemann integrable function onis
as follows:$I^{l}$. The discrepancy of the point set$P=\{x_{1,2}x, \ldots,X_{N}\}$in$I^{l}$$\mathrm{d}\mathrm{f}\mathrm{f}\mathrm{i}\mathrm{n}\alpha 1$(2.2)$D_{N}(B;P)=B \sup_{\epsilon B}|\frac{A(B;P)}{N}-\lambda_{l}(B)|$where
is a non-ernpty family of Laebesgue measurable subsets and $A(B;P)$ is the counting functionthat indicates the number of , where $1\leq n\leq N$ , for which $x_{n}\in B$ . When $J^{*}= \{\prod_{:=1}^{\iota}10,u_{i}),0\leq u_{i}<1\}$ ,the star discrepancy) isby $D_{N}^{*}(P)=D_{N}(J^{*};P)$. When $S=\{x_{1,2}x, \ldots\}$ is a sequence in , wedefineas, whereis the point set. Let be a sequence in . It is known
that the following two conditions are equivalent:$B\subset\wp(I^{l})$$n$$\mathrm{d}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\alpha 1$$D_{N}^{*}\mathrm{t}P$$D_{N}^{*}(S)$$D_{N}^{*}(S_{N})$

1.

$S$

2.

$1\dot{\mathrm{m}}_{Narrow\infty N}D^{*}(s)=0$

is$\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{f}\mathrm{o}\mathrm{m}4\mathrm{y}$$I^{l}$$S_{N}$

distributed in$I^{s}$$S$$\{x_{1},X_{2}, \ldots,x_{N}\}$$I^{s}$;.

The following clasicd theorem shows the importance of the notion of$\mathrm{d}\mathrm{i}\Re \mathrm{r}\mathrm{e}_{\mathrm{P}^{\mathrm{a}}}\mathrm{n}\mathrm{c}\mathrm{y}.\cdot$

Theorem 2.1 (Koksma-Hlawka [6]) If has boundd variation $V(f)$ on
Krause,,, we havefor any$f$$\theta\iota en$$x_{1},x_{2},$$\ldots$in the sense of Hatdy and$\overline{I}^{s}$$x_{N}\in I^{s}$$| \frac{1}{N}\sum_{\mathfrak{n}=1}^{N}f(Xn)-\int I.f(x)\ | \leq V(f)D_{N}^{*}(x1, \ldots,XN)$.

that, when $s=1$ or 2, there exists a positive constant $C$ that depends only on , andthe following inequality holds for an arbitrary point set $P$ consisting of $N$ elements:$\mathrm{S}\mathrm{d}_{1}\dot{\mathrm{m}}\mathrm{d}\mathrm{t}[12]\mathrm{s}\mathrm{h}\mathrm{o}\mathrm{w}\alpha 1$$s$$D_{N}^{*}(P) \geq C\frac{(\log N)^{s-1}}{N}$

.

(2.3)

If (2.3) holds, then there exists a positive constant $C$ that depends only on , and any sequenoe$s$satisfies$S\subset I^{\epsilon}$(2.4)$D_{N(S)}^{*}\geq c_{\frac{(\log N)^{s}}{N}}$for infinitely many $N$ . Taking account of (2.3) and (2.4), we define a low-discrepancy sequence for the one
dimensional case as follows:

Deflnition 2.1 Let$S$

be an onedimensional sequence in $[0,1)$ . If

$D_{N}^{*}(S)$satisfies$D_{N}^{*}(s)=O(N^{-}11\Re N)$

then

$S$

is called a$1\mathrm{o}\mathrm{w}A\mathrm{i}\mathrm{s}\mathrm{C}\mathrm{r}\mathrm{e}\mathrm{P}^{\mathrm{a}}\mathrm{D}\mathrm{c}\mathrm{y}$sequence.

Hereafter we consider only the case where $s=1$ . We now introxluce the classical van der Corput sequence [2] [6].

Definition 2.2 Let $p\geq 2$ be an integer. Every integer $n\geq 0$ has a unique digit expansion,$n= \sum_{\mathrm{j}=0}^{\infty}a\mathrm{j}(n)\dot{p}$in base
is

$p$

. Let

$\mathrm{d}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\alpha 1$$\phi_{\mathrm{p}}^{\tau}$$\tau=\{\tau_{\mathrm{j}}\}_{\mathrm{j}\geq 0}$$a_{\mathrm{j}}\langle n$) $\in\{0,1, \ldots,p-1\}$ for

be a set of permutations$\tau_{\mathrm{j}}$$\mathrm{a}\mathrm{U}j\geq 0$,of $\{0,1, \ldots,p-1\}$ . Then the radical-inverse functionby$\phi_{p}^{\tau}(n)=\sum_{\mathrm{j}=0}^{\infty}\tau \mathrm{j}(a\mathrm{j}(n))p^{-\mathrm{j}}-1$

The van der Corput sequence in base$p$for all integers

with digit permutations$\tau$$n\geq 0$

is the sequence.

$\{\phi_{\mathrm{p}}^{\tau}(n)\}_{n=0}^{\infty}\subset[0,1)$

Theorem 2.2 ([2|[6|) For an arbitrury ina er $p\geq 2$, the van der Corput squence in basediscrrpancy sequence.

$p$

.

is a

$lou\succ$

131

3

-adic transformation$\beta$In this section we define the fibred system and the -adic transformation, following [5] [13].
, and are the sets of all compl.g numbers, all real numbers,
integers, and natural numbers,
respectively. We also set$\beta$$\mathrm{C},$$\mathrm{R},$$\mathrm{N}$$\mathrm{Z}$$\mathrm{g}$$\mathrm{R}_{>a}$$=$$\{r\in \mathrm{R}|r>a\}$$\mathrm{z}_{\geq n}$$=$$\{i\in \mathrm{z}|i\geq n\}$$\mathrm{a}\mathrm{U}$:
md so on. For$x\in \mathrm{R},$denotae the$[x]$Definition 3.1 Let $B$ be a set md
following conditions are:$\mathrm{i}\mathrm{n}\Re^{\mathrm{e}\Gamma}\mathrm{p}\pi \mathrm{t}$

$T$

of

$x$

.

: $Barrow B$ be a map. The pair $(B,T)$ is cffial a fibrd system if the$\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{s}\mathrm{f}\mathrm{i}\alpha 1$

1. There is a ffiite countable set

2.

$A$

.

There is a map $k:Barrow A$ , md the sets
$B(i)=k^{-1}(\{i\})=\{x\in B : k(x)=i\}$form a partition of B.

3. For an arbitrary $i\in A,$
Definition 3.2 Let
derive a canonical map$T|_{B(}i$

) is

md

$\Omega=A^{\mathrm{N}}$$\varphi:Barrow\Omega$$\mathrm{i}\mathrm{n}\mathrm{j}\propto \mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e}$:$\sigma$.
be the onesidal shiffi operator. bt$\Omegaarrow\Omega$

ffom

. We

.

$\varphi(x)=\{k_{\mathrm{j}}(X)\}_{n=}\infty 1$$\varphi$$k_{\mathrm{j}}(x)=k(\dot{p}^{-1_{X}})$is calld the repraeentation map.

We have the$\mathrm{f}\mathrm{o}\mathrm{U}\mathrm{o}\mathrm{W}\mathrm{i}\mathrm{n}\mathrm{g}$commutative diagram:
$T$

$B$

$\varphi\downarrow\Omega$

Definition 3.3 If a repraeentation map

Definition 3.4 Let$\omega\in\Omega$. If$\varphi$$\omega\in{\rm Im}(\varphi),$Definition 3.5 The cylinder of rank

$n$

is

$\omega$$arrow$$arrow\sigma\varphi\downarrow\Omega$is$\mathrm{i}\mathrm{n}\mathrm{j}\propto \mathrm{t}\mathrm{i}\mathrm{V}\mathrm{e},$$\varphi$is$\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{l}\alpha 1$

a valid repraeentation.

an admissible$\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{l}\alpha 1$

defind by$B$$a_{1},$ $a_{2},$$\ldots,$$\mathrm{S}\alpha_{1^{\mathrm{u}\mathrm{e}\mathrm{n}\mathrm{o}\mathrm{e}}}$$a_{n}\in A$.

is the set.

$B(a_{1},a_{2}, \ldots, a_{n})=B(a_{1})\cap T^{-1}B(a_{2})\cap\ldots\cap T^{-}n+1B(a_{n})$We define $B$ to be a cylinder of rmk
For a$\mathrm{S}\alpha_{1^{\mathrm{u}\mathrm{e}\mathrm{n}\mathrm{o}\mathrm{e}a}}\in\Omega$$0$.

, we write the i-th elment of

Definition 3.6 Let $\beta>1$ and$\beta\in \mathrm{R}$. Let$f_{\beta}$$a$

ae $a(i)$ , that is, $a=(a(\mathrm{O}), a(1),$ $a(2),$: $[0,1)arrow[0,1)$ be the function$f_{\beta}(x)=\beta_{X}-[\beta X]$

Let$A=\mathrm{Z}\cap[0,\beta)$. Then we have the following$\mathrm{f}\mathrm{i}\mathrm{b}\mathrm{r}\alpha 1$$[0,1)$$f\beta)$$[0,1)$$\sigma$$\Omega$

The representation map$\varphi$$arrow$$\Omega$of this fibrd system is defined as follows:$\varphi(x)(n)=k$

, if

by

:

$\varphi\downarrow$$\varphi\downarrow$.

.

system $([0,1),$$arrow f_{\beta}$$\mathrm{d}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\alpha 1$$\ldots)$$\frac{k}{\beta}\leq f_{\beta}^{n}(x)<\frac{(k+1)}{\beta}$

(3.1)

132

)
) $=x$ , andwhere
proxluct topology. The
and only if there exists an integer.
We also. Let

in the product space with thebe the closure of(resp.
) ifinasfollows.
. is$\omega(n)>\omega’(n)$$\omega(n)<\omega’(n)$$\omega(k)=\omega’(k)$(resp.
).
for $k<n$ andsuch that. or equal. In this situation, we set$=f_{\beta}(f_{\beta}^{n}(X))$$\Gamma_{\beta}^{+1}\mathrm{t}x$$f_{\beta}^{\mathrm{O}}\mathrm{t}X$$n$$\succeq)\mathrm{a}\mathrm{s}\prec(\mathrm{r}\mathrm{a}\mathrm{e}\mathrm{p}$$\omega\prec\omega’$$\Omega$$\mathrm{d}\mathrm{d}\mathrm{i}\mathrm{n}\alpha 1$$\succ)$$1_{\dot{\mathrm{K}}\infty \mathrm{g}}\Gamma \mathrm{a}\mathrm{p}\mathrm{h}\mathrm{i}\mathrm{C}\mathrm{a}\mathrm{l}\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{r}\prec(\mathrm{r}\mathrm{o}\mathrm{e}\mathrm{p}$$\mathrm{d}\mathrm{f}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}\preceq(\mathrm{r}\mathrm{a}\mathrm{e}\mathrm{p}$$\Omega$${\rm Im}(\varphi)$$X_{\beta}$$\omega\succ\omega’$$\succ)$$f_{\beta}^{\hslash}(1)=a \lim_{e\nearrow 1}f_{\beta}^{\hslash}(_{X)}$,$\zeta_{\beta}=\max\{X\rho\}=\varphi(1)$,and$\rho\rho(a)=n\sum^{\infty}a(n)\beta^{-n}=0-1$.

We have the following diagram:$rightarrow f_{\beta}$$[0,1]$$[0,1]$(3.2)$\varphi\downarrow\uparrow’\rho$$\varphi\downarrow\uparrow p\rho$$\sigma$$X_{\beta}$$arrow$$X_{\beta}$

This diagram is called a -ffiic transformation.
$\beta$We use the$\mathrm{f}\mathrm{o}\mathrm{U}\mathrm{o}\mathrm{w}\mathrm{i}\mathrm{n}\mathrm{g}$notation for periodic sequences:$(a_{1}, a_{2}, \ldots,\dot{a}_{n’\cdots\dot{\mathrm{h}}m}+)$$=(a_{1},$ $a_{2},$$\ldots,$$a_{n},$$a_{\mathfrak{n}+1},$$\ldots,a_{n\neq m}$,$a_{n},$$a_{n+1},$ $\ldots,a_{n+m}$,$\ldots,a_{n+m}$,:$a_{n},$$a_{\mathfrak{n}+1},$...)

We introduoe the fouowing propoeition ffom Ito md Takahashi [5].
Proposition 3.1 For an$\sigma 0\varphi=\varphi\circ f_{\beta}$

2.

$\varphi:[0,1]arrow X_{\beta}$

S.

$\rho_{\beta}\circ\varphi=\mathrm{i}\mathrm{d}$4.

$\rho_{\beta^{\circ\sigma}}=f\rho\circ\rho\beta$$\rho_{\beta}$:

on $[0,1]$ .
on.

6. For an$t\}$

is an injoetion and is stri

$X_{\beta}arrow[0,1]$$\rho_{\beta}(\omega’)$

the folbwing statements hold in$(S.\mathit{2})$.

on $[0,1)$ .

1.

5.

$aTbib\mathrm{u}\eta\beta\in \mathrm{R}_{>1}$${\rm Im}(\varphi)$is a$Cu_{y}o’ de\Gamma-pt\mathrm{E}Sm\dot{n}ng,$

consists. The lauer coee $\alpha cursmly$ when],$t<s$ implies that$\varphi(t)\prec\varphi(s)$.

.

$\omega nu_{n}uoussu\dot{\eta a}\hslash on$$arbib\mathrm{u}\eta t\in 1^{\mathrm{o},1}$$i.e.,$$\rho_{\rho^{1}}-(t)$and is$\dot{a}the\mathrm{r}$$orde\mathrm{r}_{-}p\mathrm{f}esm\dot{n}ng,$of one point
for some $n>0$ .
$a$$\varphi(t)oT$$i.e.,$$\omega\prec\omega’$of $bvo$ points

imphes that$\varphi(t)$$\rho_{\beta}(\omega)\leq$

and $\sup\{\varphi(s)|s<$$f_{\beta}^{n}(t)=(\dot{0})$We ako remark that the following proposition holds:
Proposition 3.2$X_{\beta}=\{\omega\epsilon\Omega|\sigma^{n}\omega\preceq\zeta_{\beta}, f_{oTa}u n\geq 0\}$which satisfiae $u(i)=u(i+n)$ for any
Definition 3.7 Let. If there existisis periodic, we define the period of as $\min\{n\in \mathrm{z}_{\geq 1}|u(i)=$calld a periodic sequence. Whenfor any}.
$u\in X_{\beta}$$u\in X_{\beta}$$\mathrm{u}(i+n)$$i\in \mathrm{Z}$The following$\mathrm{d}\mathrm{e}\mathrm{f}\mathrm{i}\dot{\mathrm{m}}\mathrm{t}\mathrm{i}_{0}\mathrm{n}$$i\in \mathrm{Z},$$n\in \mathrm{z}_{\geq 1}$

md theorem are from Parry [9].

$u$

$u$

133

Definition 3.8 Whenor simple. In this case,$\zeta_{\beta}$$\beta$is periodic and its period is $m,$ and -ffiic transformation (3.2) are called Markov
equation:is the unique $z>1$ solution of the$\beta-$$\beta$$\mathrm{f}\mathrm{o}\mathrm{U}_{0}\mathrm{W}\mathrm{i}\mathrm{n}\mathrm{g}$(3.3)$z^{m}- \sum_{i=1}^{m}a_{i}-1z^{m-}i=0$

where
Markov,. This equation is cffied the characteristic equation of . Whendenotes the length of the period of .

$\zeta_{\beta}=(\dot{a}_{\mathrm{o}},a1, \ldots, am-2, (a_{m-1}-1))$$p(\beta)$$\beta$$\beta$is$\zeta_{\beta}$

Theorem 3.1 The conjugates ofrespect to its chamcterishc equation have absolute values less than 2.

$\beta\tau\dot{m}ffi$

When is not necessarily Markov, the notion of the charactenistic equation is generalized as folows. This.
function was first studied in Takahashi
and Ito and$\beta$$1^{14}1[15]$$\mathrm{I}\mathrm{h}1\mathrm{f}\mathrm{f}\mathrm{l}\mathrm{h}\mathrm{a}\mathrm{s}\mathrm{h}\mathrm{i}[5]$Definition 3.9$\phi_{\beta}(Z)=n\geq 0\sum\zeta\rho(n)(\frac{z}{\beta})^{n+1}$

We also have the following proposition from Ito and.

$\mathrm{I}\mathrm{b}]\mathrm{f}\mathrm{f}\mathrm{i}\mathrm{h}\mathfrak{B}\mathrm{h}\mathrm{i}[5]$Proposition 3.3
converges in a neighborhood of the unit disk $\{z\in \mathrm{C}||z|\leq 1\}$ and the fimction
has only one simple root at $z=1$ in a neighborhood of the unit disk.
$\phi_{\beta}(Z)$$1-\phi_{\beta}(Z)$Remark 3.1 When4$\beta$is Markov, $1-\phi_{\beta}(\beta/z)=0$ becomes the characteristic equation of$\beta$.

Constructing the sequence

In this section, a sequenoe
is defined by the use of adic transformation,and letbe atransformation (3.2). Let $B=[0,1)$ , andbe the same as in the previous section.
$N_{\beta}\subset[0,1)$$([0,1],f_{\beta,\beta}X,\sigma,\varphi, \rho_{\beta})$$\mathrm{R}_{>1}$

Definition 4.1 Let$n\in \mathrm{z}_{\geq 0}$$\beta-$$\beta- \mathrm{f}\mathrm{f}\mathrm{i}\mathrm{i}\mathrm{c}$$\mathrm{f}\mathrm{o}\mathrm{l}1_{\mathrm{o}\mathrm{w}}\dot{\mathrm{m}}\mathrm{g}[7]$$A,\Omega,$$\zeta_{\rho},$. Let$\beta\in$$B(a1, \ldots , a_{n})$. Define$\{(\dot{0})\}$$X_{\beta}(n)=$

$\{$

{

,

$\omega\in X_{\beta}|\sigma^{n-1}\omega\neq(\dot{0})$

$n=0$

and
,

$\sigma^{n}\omega=(\dot{0})$},$n\neq 0$’$\{(\omega(\mathrm{o}), \ldots,\omega(n-1))|\omega\in X_{\rho\}}$$\mathrm{Y}_{\beta}(n)=$and.

$\mathrm{Y}_{\beta}^{0}(n)=\{(a_{\mathrm{o}\cdot\cdot 1},.,a_{n-})|(a\mathrm{o}, \ldots, an-2, an-1+1)\in \mathrm{Y}_{\beta}(n)\}$Let$k\in \mathrm{Z}_{\geq 0},$$c_{\beta}^{\mathrm{o}}(n),$where$u\in \mathrm{Y}_{\beta}(k)$$\sigma_{\beta}(u;n)$$\mathrm{u}\cdot v$

, and

, and

$v\in \mathrm{Y}_{\beta}(l)$$G_{\beta}^{\mathrm{O}}(u;n;v)$. Define$\mathrm{Y}_{\beta}(u;n),$$\mathrm{Y}_{\beta}^{\mathrm{O}}(u;n),$$\mathrm{Y}_{\beta}(u;n;v),$$G_{\beta}(u;n)$,

as follows:$\mathrm{Y}_{\beta}(\mathrm{u};n)$$=$$\{u\cdot\omega|u\cdot\omega\in \mathrm{Y}_{\beta}(k+n)\}$$\mathrm{Y}_{\beta}^{\mathrm{O}}(u;n)$$=$$\{u\cdot\omega|\mathrm{u}\cdot\omega\in \mathrm{Y}_{\beta}^{\mathrm{O}}(k+n)\}$$\mathrm{Y}_{\beta}(u;n;v)$$=$$\{u\cdot\omega\cdot v|u\cdot\omega\cdot v\in \mathrm{Y}_{\beta}(k+n+l)\}$$\mathrm{Y}_{\beta}^{0}(u;n;v)$$=$$\{u\cdot\omega\cdot v|\mathrm{u}\cdot\omega\cdot v\in \mathrm{Y}_{\beta}^{\mathrm{O}}(k+n+l)\}$$G_{\beta}(n)$$=$$\#\mathrm{Y}_{\beta}(n)$$c_{\beta}^{\mathrm{o}_{(n)}}$$=$$\#\mathrm{Y}_{\beta}\mathrm{o}(n)$$G_{\beta}(\mathrm{u};n)$$=$$\#\mathrm{Y}\rho(u;n)$$G_{\beta}^{\mathrm{O}}(u;n)$$=$$\#\mathrm{Y}_{\beta}^{\mathrm{O}}(u;n)$$G_{\beta}(u;n;v)$$=$$\#\mathrm{Y}_{\beta}(u;n;v)$$\theta_{\beta}^{)}(u;n;v)$$=$$\#\mathrm{Y}_{\beta}^{\mathrm{O}}(u;n;v)$means the concatenation of$u$and , that is to say,$v$

$u\cdot v=(u(\mathrm{o}), \ldots,u(n-1), v(\mathrm{o}), v(1), \ldots)$

FinaUy we set$\mathrm{Y}_{\beta}^{\mathrm{O}}(u;n;v),.G\rho(n),$$\mathrm{Y}_{\beta}(\mathrm{O})=\mathrm{Y}_{\beta}^{\mathrm{o}}(0)=\{\epsilon\}$.

where is the empty word and satisfies$\epsilon$$\epsilon\cdot \mathrm{u}=u\cdot\epsilon=u$

for any$u\in \mathrm{Y}_{\beta}(n)$

.

134

Definition 4.2 Define the-left lexicographical order
only if $(\omega(n-1), \ldots,\omega(0))\prec(d(m-1),\ldots,\omega’(0))$ wherein$r-l\prec$$\mathrm{r}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{b}\mathrm{t}\infty$$\mathrm{m}_{=0^{X}}\beta(n)$$\omega\in X_{\beta}(n)$Definition 4.3
that is,$L_{\beta}$isDefine$(N_{\beta}[7])$$L_{\beta}=\{\omega:\}_{i=}^{\infty}0$

as a set and$\mathrm{f}\mathrm{f}_{=0}X_{\beta}(n)$$\omega:^{r-l}\prec\omega_{\dot{f}}$as$\mathrm{f}\mathrm{f}_{=0}X_{\beta}(n)$holds forandas$\mathrm{f}\mathrm{o}\mathrm{l}1_{\mathrm{o}\mathrm{W}\mathrm{S}}.\cdot\omega r-l\prec d$$\omega’\in X_{\beta}(m)$.

if andorderal in right-to-leR lexicographical order,$\mathrm{a}\mathrm{U}i<j$. Then, the sequenoe

is defined as follows.

$\cdot$$N_{\beta}$$N_{\beta}=\{\rho\beta(\omega i)\}^{\infty}i=0^{\cdot}$

Example 4.1 If$\beta=\frac{1+\sqrt{5}}{2}$, then$\zeta_{\beta}=(\mathrm{j},\dot{0})$and dements of$N_{\beta}$

are calculatd as follrs:$N_{\beta}(\mathrm{o})$$=$$\rho_{\beta}(\mathrm{o})=0$$N_{\beta}(1)$$=$$\rho_{\beta}(1)=0.618033988749895\ldots$$N_{\beta}(2)$$=$$\rho_{\beta}(01)=0.3819660112501m\ldots$$N_{\beta}(3)$$=$$\rho_{\beta}(\mathrm{m}1)=0.23606797749979\ldots$$N_{\beta}(4)$$=$$\rho_{\beta}(101)=0.854101966249686\ldots$$N_{\beta}(5)$$=$$\rho_{\beta}(\mathrm{t}\mathrm{K}\mathrm{n}1)=0.145898033750316\ldots$$N_{\beta}(6)$$=$$\rho_{\beta}(1\alpha 11)=0.763932022500212\ldots$$N_{\beta}(7)$$=$$\rho_{\beta}(0101)=0.527864045\alpha \mathrm{n}422\ldots$$N_{\beta}(8)$$=$$\beta\rho(\alpha \mathrm{x}\mathrm{n}\mathrm{l})=0.0901699437494747\ldots$$N_{\beta}(9)$$=$$\rho_{\beta}(1\alpha]01)=0.70820393249937\ldots$$N_{\beta}(10)$$=$$\rho_{\beta}(01\alpha 11)=0.472135954999581\ldots$$N_{\beta}(11)$$=$$\rho_{\beta}(\alpha 1101)=0.326237921249265\ldots$$N\rho(12)$$=$$\rho_{\beta}(10101)=0.944271909999161\ldots$$N_{\beta}(13)$$=$$\rho_{\beta}(\mathrm{m}0001)=0.05572809\alpha \mathrm{x}\mathrm{n}8416\ldots$$N\rho(15)$$=$$\rho_{\beta}(100001)=0.673762078750737\ldots$$N_{\beta}(16)$$=$$\rho_{\beta}(010W1)=0.437694101250947\ldots$:
Rom this$\mathrm{d}\mathrm{e}\mathrm{f}\mathrm{i}\dot{\mathrm{m}}\mathrm{t}\mathrm{i}_{0}\mathrm{n}$Proposition 4.1 If
pmnutabms$di\dot{\varphi}t$$\beta$, we in; an$\tau_{\mathrm{j}}=\mathrm{i}\mathrm{d}$$\mathrm{l}\mathrm{m}\alpha \mathrm{l}\mathrm{i}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{l}\mathrm{y}$have the fouowing proposition:$int_{\mathfrak{B}^{ef}}g’ wtef$.

than 2 ffien$N_{\beta}$

is the van der$c_{\mathit{0}}\eta u\iota$

Rom
md Propoeition 4.1, we sae that if
then
is a
is to say, $D_{M}^{*}(N_{\rho})=O(M^{-1}\log M)$ holds for ffi. We ako have thesquence in base$\beta$urith all$\mathrm{T}\mathrm{h}\infty \mathrm{r}\mathrm{e}\mathrm{m}2.2$$\beta\in \mathrm{z}_{\geq 2}$$N_{\beta}$$\beta\in \mathrm{z}_{\geq 2}$

Theorem 4.1 Let$(\mathrm{P}\mathrm{V})$Au$zef\eta es$$\beta$ofbe a $fwl$ numbef$1-\phi_{\beta}(Z)$$gi\mathrm{W}te\mathrm{r}$$1\mathrm{o}\mathrm{w}\triangleleft \mathrm{i}_{\mathrm{S}\mathrm{C}\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{y}}\mathrm{m}\mathrm{C}\mathrm{s}\alpha 1^{\mathrm{u}}\mathrm{e}\mathrm{n}\mathrm{o}\mathrm{e}$, that:$\mathrm{f}\mathrm{o}\mathrm{u}_{0}\mathrm{w}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}\infty \mathrm{r}\mathrm{e}\mathrm{m}$than 1, and let the$foll_{\mathit{0}}u\dot{\hslash}ng$

condihon$(\mathrm{P}\mathrm{V})$hold:oecept $fofz=1$ bebng to $\{z\in \mathrm{C}||z|>\beta\}$ .

Then,$D_{M}^{*}(N_{\beta})=o( \frac{(\log M)^{2}}{M})$$hou_{S}$.

$M_{oTwve}\mathrm{r},$i.f is$\beta$$Mark_{\mathit{0}}v$, then$D_{M}^{*}(N_{\rho})=o( \frac{1_{\mathfrak{B}}M}{M})$$hou_{S}$.

Remark 4.1 When is Markov, the conditionisto the condition that dl conjugaffi ofwith raepect to its characteristic
belong to $\{z\in \mathrm{C}||z|<1\}$ .
$\beta$$(\mathrm{P}\mathrm{V})$$\alpha_{1^{\mathrm{u}\mathrm{i}_{\mathrm{V}\mathrm{a}}1\mathrm{e}\mathrm{n}}}\mathrm{t}$$\alpha_{1}\mathrm{u}\mathrm{a}\mathrm{t}\mathrm{i}_{0}\mathrm{n}(3.3)$

Remark 4.2 In [7], the case in which$\beta$is Markov is.

$\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{v}\alpha 1$$\beta$135

To prove this$\mathrm{t}\mathrm{h}\infty \mathrm{r}\mathrm{e}\mathrm{m}$, we provide lemmas and definitions. We use the following notations:,$(\omega(i), \ldots,\omega \mathrm{C}-1))$

$i<j$

,

$i=j$

$\omega 1^{i},j)=\{$$\epsilon$

’

where
and
. $R_{\beta}(u)=\lambda(B(u))$ wheoe is theLebesgue measure, $u\in X_{\beta}(n)$ ,and $B(u)$ is the cylinder (3.5). For a sequenoe $S,$ $S[N1$ denotes the point set consisting of the first $N$ elementsof , and $S[N;M]=S[N+M]\backslash S[N]$ .
$\omega\in X_{\beta}$$i,j\in \mathrm{z}_{\geq 0}$$\lambda$$\mathrm{o}\mathrm{n}\triangleright\dim\alpha 1\mathrm{f}\dot{\mathrm{f}\mathrm{l}}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}$$S$

Definition 4.4 For any $k\geq 0$ and$u\in \mathrm{Y}_{\beta}(k)$, define$e(u)=\{i\in \mathrm{Z}_{\geq 0}|\zeta_{\beta}[\mathrm{o},i+1)\cdot u\not\in \mathrm{Y}_{\beta}(k+i+1)\}$

Lemma 4.1 ([5|) For an arbibury $k\geq 0$ and$u\in \mathrm{Y}_{\beta}(k)$, we have the.

$f_{oll_{\mathit{0}}ng\mu \mathit{0}}u\dot{n}maning$of$\mathrm{Y}_{\beta}(u;n)$:$\mathrm{Y}_{\beta}(u;n)=\mathrm{u}\mathrm{Y}_{\beta}^{\mathrm{o}}(u;j)\cdot\zeta\beta[\mathrm{o},n-j)\mathrm{u}\max\{\mathrm{Y}\rho(u;n)\mathrm{j}=1n\}$

Proof. It is trivial to show that theIfsatisfies-hand side includes theand$1\mathrm{f}\mathrm{f}\mathrm{i}-$$v=(a_{1,\ldots,+k}a_{n})\in \mathrm{Y}_{\beta}(u;n)\backslash \mathrm{Y}_{\beta}^{\mathrm{O}}(u;n)$$\mathrm{r}\mathrm{i}\mathrm{g}_{1}$-hand side
, then there exists an integer$v \neq\max\{\mathrm{Y}_{\beta}(u_{1}n)\}$

$l$

that

$k+1\leq l\leq n+k$

and$\min\{w\in \mathrm{Y}_{\beta}(u;n)|w\succ v\}=(a_{1},\ldots , a_{l}+1,0, \ldots, 0)$.

This means that$(al+1, \ldots,a_{n}+k)=\zeta_{\beta}10,n+k-l)$and$(a_{1}, \ldots , a_{l-1}, a_{l}+1)\in \mathrm{Y}_{\beta}^{\mathrm{O}}(u;l-k)$

hold.
Taking account of Lemma 4.1, we give the following definition:

Definition 4.5 For an arbitrary$\square$, define an integer $d(u)$ as followa $d(u)=k$ if$u\in \mathrm{Y}_{\beta}(n)$$u\in \mathrm{Y}_{\beta}^{\mathrm{O}}(k)\cdot\zeta_{\rho}10,n-k)$

holda Remark that$\max\{\mathrm{Y}_{\beta}(n)\}=\zeta_{\beta}[0,n)$.

From Lemma 4.1, Definition 4.4, and Definition 4.5 we have the following lemma.
Lemma 4.2 For any$k,$ $l,n\geq

0,$$u\in \mathrm{Y}_{\beta}(k)$, and$v\in \mathrm{Y}_{\beta}(l)$, we have the follouing paffiboning of$\mathrm{Y}_{\beta}(u;n;v)$$n-j-1\leq j\leq n\mathrm{u}\mathrm{Y}(\rho^{\mathrm{O}};ju)\cdot\zeta_{\beta[}1\not\in e(v)\mathrm{o}_{n-},j)$, if $n+k-d( \max\{\mathrm{Y}_{\rho(}u;n)\})-1\in e(v)$$\cong\{$,$n-j-1 \leq j\leq \mathrm{u}\mathrm{Y}^{\mathrm{O}}(\beta u1\not\in^{n}\mathrm{e}(v).\beta|j)\cdot\zeta 10,n-j)\mathrm{u}\max\{\mathrm{Y}_{\beta()\}}u;n$Lemma 4.3 For any $n\geq 0$ and$u\in \mathrm{Y}_{\beta}(n)$,$R_{\beta}(u)= \frac{1}{\beta^{d(u)}}(1-\sum_{i=0}^{n-d(}\frac{\zeta_{\beta}(i)}{\beta^{t+1}}\mathrm{I}u)-1$

holds.

othefwrise.

$\mathrm{Y}_{\beta}(u;n;v)$

:

136

Proof. Let$u=u^{\mathrm{O}}\cdot\zeta_{\rho}[0,n-d\mathrm{t}u))$where$u^{\mathrm{O}}\in \mathrm{Y}_{\beta}^{\mathrm{O}}(d(u))$. FVom Defimition 3.6,

$R_{\beta}(u^{\mathrm{O}})= \rho_{\beta}((u^{\mathrm{o}\mathrm{O}}(0), \ldots,u(d\mathrm{t}u)-1)+1)-\rho_{\beta}\mathrm{t}(u^{\mathrm{o}}(0), \ldots,u^{\mathrm{o}}(d(u)-1))=f\frac{1}{fl^{\langle u)}}$and.

$R_{\beta}( \zeta_{\beta}[0,n-d\mathrm{t}u)))=1-\sum_{\mathrm{o}i=}^{1}\frac{1}{\beta^{i+1}}n-4(\mathrm{t}l)-$When$v\cdot w\in \mathrm{Y}_{\beta}(m)$, it follows that $R_{\beta}(v\cdot w)=R_{\beta}(v)R\rho(w)$ . Then, the lffllma holds.

$\square$Remark 4.3 Rom Definition 3.6, it follows that$f_{\beta}(x)= \beta^{n}(x-.\cdot\sum_{=0}^{n}-1\frac{\varphi(x)(i)}{\beta^{i+1}})$for any $x\in[0,1]$ and $n\geq 0$. Then, we have
$R_{\beta} \langle u)=\frac{1}{\beta^{n}}f_{\rho}^{n}-d(\tau*)(1)$

for any$u\in \mathrm{Y}_{\beta}(n)$and $n\geq 0,$$\mathrm{h}\mathrm{o}\mathrm{m}$Lemma 4.3.

Lemma 4.4
Letr be the absolute value of thesmallest zerv of, there aists a constant $C_{E}>0$ andThen for any small$s\alpha:ond$$([\mathrm{S}])$$1-\phi_{\beta}(Z)$, that is, $r= \min\{|z||z\in \mathrm{C},$ $z\neq]$$\epsilon>0$$|G_{\beta}^{\mathrm{o}_{(n}}u;)- \frac{\beta^{n+k}R_{\beta}(u)}{\psi_{\rho^{(1)}}},|\leq\frac{C_{\epsilon}}{n}(\frac{\beta}{r-\epsilon})^{n}$hous for any $n\geq 0,$ $k\geq 0$ andProof. Let$k\geq 0$

and$u\in \mathrm{Y}_{\beta}(k)$$u\in \mathrm{Y}_{\beta}(k)$.

. Remark that
$R_{\beta}(u)= \sum R\rho(u\cdot v)u\cdot v\in \mathrm{Y}_{\rho(:}un)$(4.1)

holds. From (4.1), Lemma 4.1, and Remark 4.3, we have$\beta^{n+k}R_{\beta}(u)=\sum_{\mathrm{j}=0}^{n-1}f^{\mathrm{j}}\beta(1)G^{\mathrm{o}}\beta(u;n-j)+f_{\rho^{\#}}^{n}(1)$where $l=k-d( \max\{\mathrm{Y}_{\rho}(u;n)\})\geq 0$.

$\mathrm{R}\mathrm{f}\mathrm{f}\mathrm{l}1\mathrm{a}\mathrm{r}\mathrm{k}$(4.2)

that the formal power series$\sum_{n\geq 1}Z^{n}\sum_{\mathrm{j}=0}^{n-1}f_{\beta}\mathrm{j}(1)G\mathrm{O}(\beta u;n-j)\beta-(n+k)$

converges for $|z|<1$ . We have the following equality from (4.2):}$\beta^{k}\sum_{n\geq 1}z^{n}R\beta(u)=\sum_{n\geq 1}(\frac{z}{\beta})^{n}=\sum_{\mathrm{j}\mathrm{O}}^{n-1}f^{n}\rho(1)(\mathscr{S}$$( \beta u;n-j)+\sum_{n\geq 1}(\frac{z}{\beta})nf\rho(n+\iota 1)$

We also have$\sum_{n\geq 1}(\frac{z}{\beta})^{n}\sum^{n-1}f_{\beta}^{j}(1)\sigma\}(\rho u;n-j)\mathrm{j}=0$$= \sum_{\mathrm{j}\geq 1n}\sum_{\mathrm{j}\geq}f_{\rho\rho}^{\mathrm{j}\mathrm{o}_{(u\cdot}}-1(1)Gn-j+1)|(\frac{z}{\beta})^{n}$$= \sum_{\mathrm{j}\geq 0}f_{\rho}^{\mathrm{j}}(1)(\frac{z}{\beta})^{\mathrm{j}}\sum_{n\geq 1}G_{\rho}^{\mathrm{o}}(u;n)(\frac{z}{\beta})^{n}$

(4.3)

137

and, from Remark 4.3,$(1-Z) \sum n\geq 0f_{\beta}^{\hslash}(1)(\frac{z}{\beta})^{n}$$=(1-z)+(1-Z) \hslash\geq\sum_{1}(1-\sum_{=i\mathrm{O}}^{n-1}\frac{\zeta_{\beta}(i)}{\beta^{i+1}})zn$$=1- \frac{\zeta_{\beta}(0)}{\beta}+\sum_{2n\geq}(1-z)(1-\sum_{\dot{*}=0}^{\hslash-1}\frac{\zeta_{\beta}(i)}{\beta^{i+1}})zn$$=1- \sum_{\geq n\mathrm{O}}\zeta_{\rho}(n)(\frac{z}{\beta})^{n+1}=1-\phi\rho(Z)$By using thaee two equalities, we$\mathrm{o}\mathrm{b}\mathrm{t}\mathrm{f}\dot{\mathrm{f}\mathrm{i}}\mathrm{I}\mathrm{l}$.

from (4.3) that$\sum_{n\geq 1}\sigma_{\rho}(u;n)(\frac{z}{\beta})^{n}=\frac{z\beta^{k}R_{\beta}(u)}{1-\phi\rho(z)}-\frac{(1-z)\sum_{n\geq}1f\beta^{+t}(1)(z/\beta)^{n}}{1-\phi\rho(z)}$

.

(4.4)

Consider the function$h_{1*}(z)=$$\sum_{n\geq 1}((\mathscr{S}^{)}(u;n)\beta(\frac{z}{\beta})n-\frac{\beta^{k}R\rho(u)}{\phi_{\beta}(1)}zn)$

(4.5)
$=$

$\frac{z\beta^{k}R_{\beta}(u)}{1-\phi_{\beta}(z)}-\frac{(1-z)\sum\hslash\geq 1f_{\rho}^{n^{\mu}}(1)(_{Z/\rho)}n}{1-\phi_{\beta}(z)}-\frac{z\beta^{k}R_{\beta}(u)}{(1-z)\emptyset_{\beta}(1)}$.

comes from (4.4). Rom Proposition 3.3, we see that. is analytic in a neighborhood$\lim_{zarrow1}(1-Z)hu(Z)=0$(4.5)
of. We also see fromthat
. Considering the fact
$k\geq 1$ and that the second term of the right-hand side of (4.4) and its
thatfor any
derivative are bounded uniformly in , we see that there exists a constantand$h_{u}(z)$$\mathrm{T}\dot{\mathrm{h}}\mathrm{e}\mathrm{s}\mathrm{e}\omega \mathrm{n}\mathrm{d}\mathrm{e}’\dot{\mathrm{q}}\mathrm{u}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{t}\mathrm{y}$$\{z\in \mathrm{C}||z|\leq r-\epsilon, z\neq 1\}$$\beta^{k}R\rho(u)\leq 1$$u\in \mathrm{Y}_{\beta}(k),$$l$$C_{\epsilon}$(4.6)$k \geq 1,u|z|=\sup|\epsilon r-\mathrm{Y}_{\rho,\epsilon}(k)h’(uZ)|<c_{\mathrm{g}}$holds. Then we have$n!| \frac{\sigma_{\beta}(u;n)}{\beta^{n}}-\frac{\beta^{k}R_{\beta}(u)}{\phi_{\beta}’(1)}|=$and the lemma$|h_{\mathrm{u}}^{(n)}(0)|$$==$$|^{\frac{d^{n-1}h_{u}’}{\frac{dz(n-1n-1(\mathrm{o})!)}{2\pi(r-\epsilon)n}}1} \int_{|z\mathrm{I}r}=-\epsilon)h_{u}’\mathrm{t}Zdz|$$\leq$$(n-1)! \frac{C_{\epsilon}}{(r-\epsilon)^{n}}$.

$\square$$\mathrm{f}\mathrm{o}\mathrm{U}\mathrm{o}\mathrm{w}\mathrm{s}$Lemma 4.5 If
following statements:$\beta\in \mathrm{R}_{>1}$

1. For an arbibufV

is Markov and$v\in X_{\beta},$$\zeta_{\beta}=(\dot{a}_{\mathrm{O}\cdot\cdot m-2},., a, (a_{m-1}-1))$$\{\sigma_{\rho^{(n}})\}^{\infty}n=0$

and$\{G_{\beta}(n)\}n=0\infty$, where $m=p(\beta)$ , then we have thesatish the following$bn$$G \rho(\epsilon;n+m;v)-\sum_{i=0}a_{i}G\rho(\epsilon;n+m-i-1;v)=0m-1$

2. For arbitrary$\mathrm{u}\in \mathrm{Y}_{\beta}(k),$$k\geq m$and$v\in X_{\beta}$, the$f_{oll\alpha}f\dot{fl}ng$

ear recurrent equation:.

equation holds for any $n\geq m-k+d$ :$\sum_{i=1}^{m-}a_{k}-d+iG\rho(\epsilon;n-i;v)k+d$

when $d>k-m$$G_{\beta}(\epsilon;n;v)$

when $d=k-m$$G_{\beta}(u;n;v)=\{$

where $d=d( \mathrm{u}[\max\{0,k-m+1\}, k+1))+k-m$.

(4.7)

(4.8)

138

. From Proposition 3.2, we have the following$p_{1}mf$$\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{t}\mathrm{i}_{0\mathrm{n}}\dot{\mathrm{m}}\mathrm{g}\cdot$.

.

$\mathrm{Y}_{\beta}(\epsilon;n+m;v)=\mathrm{u}m\dot{\mathrm{J}}^{=}0:=1\alpha i^{1}\mathrm{u}\zeta\rho \mathrm{l}0,.j)\cdot i\cdot \mathrm{Y}\rho(\epsilon\cdot n+|- mj- 1;v\mathrm{o}\cdot)$

When $d=k-m$, it is trivial tothisfollowing partitioning from the same proporition.
$\mathrm{o}\mathrm{b}\mathrm{t}\dot{\mathrm{a}}\iota 1$$\mathrm{P}^{\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}}\dot{\mathrm{m}}\mathrm{g}$from Proposition 3.2. When $d>k-m$, we obtniIl the$\mathrm{Y}_{\rho}(u;n.\cdot v)=m\dot{\mathrm{J}}=\overline{\mathrm{u}}\mathrm{u}^{i}u\cdot i\cdot \mathrm{Y}\beta \mathrm{t}\epsilon;n-j;v)1k+dt\mathrm{r}_{i}-\ell+-1=0-$

The lemma follows from these partitioninae.
Proof of Theorem 4.1. Let$M$ to satisq $m>k$ . Define$\cdot$$k>0_{1}u\in \mathrm{Y}_{\beta}(k)$. Laet$M,$.

$\in \mathrm{N}$.

..

$\square$and $b=(k.’ b_{1}, \ldots,b_{m}-1)\backslash |=L_{\beta}(M)$ . We assume$\Delta(I;P)=A(I;P)-Mx(I)$,where is an interval in $[0,1)$ and $P=\{x_{1,2}X, \ldots,x_{M}\}\subset[0,1)$ . For any finite sets of points $P,P’$ in $[0,1)$
and any,$I$$\mathrm{i}\mathrm{n}\mathrm{t}_{-}\mathrm{g}\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{s}I,I’\subset[0,1),$$I\cap I’=\emptyset$$\Delta(I;P\mathrm{u}P)$$=$$\Delta(I;P)+\Delta(I;P’)$$\Delta(I\mathrm{u}F;P)$$=$$\Delta(I;P)+\Delta(I’;P)$(4.9)

hold. Here,is the disjoint union of $P$ and $P$ or the union of $P$ and $P’$ with multiplicity. Rom
Dffinition 4.3 and (4.9), we have
$P\mathrm{u}P’$$\Delta(B(u);N\rho[M])$$=\Delta(B(u);\overline{\mathrm{u}}_{\mathrm{O}}m1\iota_{\mathrm{j}\overline{\mathrm{u}}}1\dot{g}=:=0\mathrm{Y}\rho(\epsilon;j;vi\mathrm{j}))$(4.10)$= \sum_{\mathrm{j}=0i}^{m-1}\sum_{=0}^{1}\Delta \mathrm{t}B(u);\mathrm{Y}\rho \mathrm{t}\epsilon\cdot j|;v:\mathrm{j}\iota_{\dot{g}^{-}}))$

where). Consider the $0\leq j\leq k$ part of the right hand side of (4.10).

$v_{\dot{*}\dot{f}}=i\cdot b\beta+1,m$(4.11)$\sum_{\mathrm{j}=0\dot{l}}^{kb}\sum_{=1}^{1}j-|\Delta(B(u);\mathrm{Y}\beta(\epsilon ij;v_{*}\mathrm{j}))|\leq\sum_{\mathrm{j}=0}^{k}([\beta]+1)G_{\beta}(j)R_{\rho}(u)$holds from the defimition of$\Delta$. Since$R_{\beta}(u)\leq\beta^{-k}$and$G_{\beta}(\dot{g})\leq([\beta]+1)^{\mathrm{j}}$, there exists a constant$C_{\mathrm{O}}$, and$\sum^{k}([\rho]+1)c_{\beta[j})R_{\beta}(u)<c\mathrm{O}$$\mathrm{j}=0$

is satisfied for any$k$. Then,$\mathrm{h}\mathrm{o}\mathrm{m}(4.10)$

and (4.11), we have
( $B(u)$ ; Yp$\Delta(B(u);N\beta[M])\leq c_{\mathrm{o}}+\sum_{\mathrm{j}=k+}^{m-}11b_{\mathrm{j}\sum_{1}}.=0-1|\Delta$$(\epsilon;j;v_{i}\mathrm{j})$

) .
$|$

(4.12)

Definefor$u\in \mathrm{Y}_{\beta}(k)$$\delta(u;n)$$=$$c_{\beta}^{0}(u;n)- \frac{\beta^{n+k}R_{\beta(u)}}{\phi_{\beta}(1)}$$\delta(n)$$=$$G_{\beta}^{0}(n)- \frac{\beta^{n}}{\phi_{\beta}’(1)}$and $k,n\geq 0$ . Rom this definition,$|\Delta(B(u);\mathrm{Y}_{\beta}^{0}(n))|$$=$$|\sigma_{\beta}(u;n)-R\beta(u)\sigma\rho(k+n)|$$=$$|\delta(u\cdot n)|-R_{\beta(u)(k}\delta+n)|$(4.13)

139

holds. Then, from Lemma 4.2 we have$=k \sum_{\mathrm{j}+1}^{m-}1\iota\sum_{=:\mathrm{O}}^{g^{-}1}|\Delta(B(u);\mathrm{Y}\beta(\epsilon;j;vi\mathrm{j}))|$(4.14)$\leq\sum_{=\mathrm{j}k+1i}^{m-1}\sum_{=0}\iota_{\mathrm{j}}-1(_{\mathrm{j}1}-\iota-\not\in \mathrm{e}(v.|\sum_{)\dot{2}}.\Delta(B(u);\mathrm{Y}^{\mathrm{o})}(l)\cdot\zeta\rho[\mathrm{o},j-l))|l=1\ldots..\mathrm{j}\rho+1$$\leq\sum_{\dot{g}=k+1}^{m-}1b\sum_{\dot{*}=0}^{\dot{J}}-1(_{l=1}\sum^{j}|\Delta(B(u);\mathrm{Y}_{\beta}\mathrm{o}(l))|+1)$

From the$(\mathrm{P}\mathrm{V})$.

condition and Lemma 4.4, there exist $r>\beta$ and a constant$C_{r}$

that$\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{S}6^{r}$(4.15)$| \delta(u;n)|\leq\frac{C_{r}}{n}(\frac{\beta}{r})^{\mathfrak{n}}$for any $n,$ $k>0$ and$u\in \mathrm{Y}_{\beta}(k)$. Rom (4.12), (4.13), (4.14), (4.15), and$r>\beta$, we see that$\Delta(B(u);N\beta[M1)$$\leq c_{\mathrm{o}}+c_{r}([\beta]+1)\sum_{k\mathrm{j}=+1}^{m-1}(\sum_{\iota=1}^{j}(\frac{1}{l}(\frac{\beta}{r})^{\iota}+\frac{1}{k+l}(\frac{\beta}{r})^{k+\iota_{R}}\beta(u))+1)$(4.16)$=O(m)=o(1\mathrm{o}\mathrm{e}M)$holds.

Choose an arbitrary $t\in[0,1)$ . Letof rank $m$ that satisfies

and $L_{\beta}(M)=(b_{0}, \ldots , b_{m-1})$ . Let$t\in B(t_{\mathrm{o}}, \ldots,t)m-1$ . Then we have$M\in \mathrm{N}$$B(t_{0,\ldots,1}t_{\pi\iota-})$be a cylinder,$[0, t)=B_{s_{1}}\mathrm{u}B_{\theta}\mathrm{u}2\ldots \mathrm{u}Bsk\mathrm{u}R$

where $0\leq s_{1}<s_{2}.<\ldots<s_{k}=m-.1,$(4.16), we have$B_{s}$. is a cylinder of rank$s_{i}$

and $\lambda(R)<\beta^{-m+1}$ . Then from (4.9) and$|\Delta([0,t);N1\beta M1)|=O((\log M)^{2})$,and therefore$D_{M}^{*}(N_{\beta})=o( \frac{(\log M)^{2}}{M})$.

In the following part, we consider the case in which is Markov. Let $l=p(\beta)$ andThen, is the unique $z>1$ solution of$\beta$.

$\zeta_{\beta}=(\dot{a}_{\mathrm{O}}, \ldots,a_{l-2}, \langle a_{l-1}-1))$$\beta$$d-. \cdot\sum_{=0}^{\iota_{-}1}aiz-i=0\iota_{-1}$Let$\alpha_{1},$$\ldots,$$\alpha_{q}$be the oonjugates of$\beta$with$\mathrm{r}\propto_{\mathrm{I})\propto \mathrm{t}}$.

(4.17)

to the equation (4.17), that is,:$z^{\iota}- \sum_{i=0}^{-}a_{i}Z--i(Z-\beta)\prod^{q}t1(=z-\alpha_{i})^{1}l1i=1$

where$l_{i}\geq 1,$$\alpha_{i}\neq\alpha_{\mathrm{j}}$for all $i\neq j$ and $\sum_{i=1}^{q}l_{i}=l-1$ . We also have$|\alpha_{i}|<1$

for all $i\in\{1, \ldots, q\}$

(4.18)

condition. Let. From Lemma 4.5, there exist complex numbers$\ldots l_{i}-1)$ thatthe following equation:from the$0,$,$v\in X_{\beta}$$(\mathrm{P}\mathrm{V})$$c,$$c_{i\mathrm{j}}(i=1,$ $\ldots,q,$$j=$$\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{S}6^{\Gamma}$$G_{\beta}( \epsilon;n;v)=c\beta^{n}+.\cdot\sum_{=1\mathrm{j}}^{r\iota}\sum_{=0}^{-}1c\iota_{\mathrm{j}}n\alpha_{i}\mathrm{j}n$for all$n\in \mathrm{N}$.

(4.19)

140

Rom Lemma 4.3, Lemma 4.5, and (4.19), we have$\Delta(B(u);N_{\beta}1G\beta \mathrm{t}\epsilon;k+n;v)1)$,$\sum_{h=1}^{\iota}\sum_{\mathrm{j}=0}^{1}C_{h\dot{g}()}qh-n\dot{\mathrm{J}}\alpha_{h}n-\frac{1}{\beta^{k}}(k+n)^{\mathrm{j}}\alpha hk4m$(4.20)

when $d=k-l$$=\{$$:=kd \sum_{-}^{l-}a_{i}\sum_{h=1\mathrm{j}}\sum^{\sim-1}1ql=0C_{h(\mathrm{j}}\dot{\mathrm{J}}(k+n-d)a^{kd}--:-h\frac{1}{\beta^{4+i}}+n(k+n)^{\mathrm{j}}\alpha h^{+*})k\mathrm{r}$,when $d>k-l$, and $d=d(u[ \max\{0, k-l+1\}, k+1))+k-l$. From (4.9), (4.12), (4.14), (4.18), andwhere
for any cylinder $B(u)$ of any rank
, there exists a constant $C$ that satisfies the following
and $M>G_{\beta}(l+d)$ .
$|\Delta(B(u);N_{\beta[M]})|<C$(4.21)$u\in \mathrm{Y}\rho(k),$ $n\in \mathrm{N}$$(4.\mathfrak{U}1)$$\mathrm{i}\mathrm{n}\alpha_{1}\mathrm{u}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{t}\mathrm{y}(4.21)$$k$Then, we obtain$D_{M}^{*}(N_{\rho})=o( \frac{1_{\mathfrak{B}}M}{M})$by the above reasoning.

口

参考文献[1] Guy Barat and Peter J. Grabner, Distribution properties of(1996 Sept.), 103-123.
lh-additive inctions, Journal of Number$\mathrm{G}-$$eo\mathrm{r}y60$[2] Henri Faure, Discr\’epances de suite associ\’ee \‘a un syst\‘em de num\’eration (en dimension un), BulL Soc.
Math. Fhance 109 (1981), 143-182.
[3] Henri Faure, Good permutations for extreme discrepancy, Joumal of Number Theory 42 (1992), 47-56.

[4] Peter Helekalek, Ergodicity of a class of cylinder flows related to irregularities of distribution, Compositio
Mathematica 61 (1987), 129-136.
[5] Shunji Ito and Y\={o}ichir\={o} Takahashi, Markov subshifts and realization of
Mathematical Society of Japan 26 (1974), 33-55.

,$\beta-\Theta \mathrm{C}\mathrm{p}\mathrm{a}\mathrm{n}\mathrm{S}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s}$Joumal of the[6] Harald Niederreiter, Random Number Genemtion and Quasi-Monte Carlo Methods, CBMF-NSF Regional
Conference Series in Applied Mathematics, SIAM, 1992.
[7] Syoiti Ninomiya, Constructing a new class of low-discrepancy sequences by using the -ffiic transformation,
Mathematics and Computers in Simulation (to appear).
$\beta-$[8], Van der Corput sequences, Kakutani transforms and one-dimensional numerical integration,
Joumal of Computabonal and Appliai Mathematics 44 (1992), 21-39.

$\mathrm{G}\mathrm{i}\mathrm{U}\mathrm{o}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{g}\grave{\alpha}$[9] William Parry, On the$P\mathrm{e}\mathrm{x}\mathrm{p}\mathrm{a}\mathrm{n}\mathrm{s}\mathrm{i}_{0}\mathrm{n}\mathrm{S}$of real numbers, Acta Math Acad. Sci. Hungar. 11 (1960), 401-416.

[10] Karl Petersen, $E\eta diC$ Theory, Cambridge University Press, 1983.
[11] A. R\’enyi, Representations for real numbers and their ergodic properties, Acta Math. Acad. Sci. Hungar.
8 (1957), 477-493.
[12] W. M. Schmidt, Irregularities of distribution VII, Acta Arith. 21 (1972), 45-50.
[13] Frits Schweiger, $E\tau gdiC$ Theory of Fibmt Systems and$Meb\dot{\mathrm{v}}c$

Number Theory, Oxford Scienoe Publica-

tions, 1995.

[14]

Takahashi, -transformations and symbolic dynamuics, Pruc.
Japan-USSR$Pn’ babilityThw\mathrm{r}y$, Lecture Notes in Mathematics 330, Springer, (1973), 454-464.

$\mathrm{Y}\overline{\mathrm{o}}\mathrm{i}\mathrm{c}\mathrm{h}\mathrm{i}\mathrm{r}\overline{\mathrm{O}}$$\beta$$s_{\alpha \mathrm{i}on}d$$S_{\Psi}nb_{\mathit{0}\dot{\Re}}um$

on

141

[15]

Takahashi, Shffi with orbit basis and ralization of(1983), 599-629 (Correction: 21(1985), 637).

$\mathrm{Y}\overline{\mathrm{o}}\mathrm{i}\mathrm{d}\dot{\mathrm{u}}\mathrm{r}\overline{\mathrm{o}}$$\mathrm{o}\mathrm{n}\triangleright\dim\alpha \mathrm{l}\dot{\mathrm{g}}0\mathrm{n}\mathrm{a}\mathrm{l}$maps, Osaka$MaV\iota$

J. 20