## Paper folding, digit patterns and groups of arithmetic fractals.(English)Zbl 0694.10009

This paper is devoted to pattern sequences and paper folding previously studied by several authors [see infra]. A binary pattern P (i.e., a finite string of 0’s and 1’s) gives rise to a pattern sequence $$a_ P$$ defined by $$a_ P(n):=(-1)^{e_ P(n)},$$ where $$e_ P(n)$$ is the number of occurrences of the pattern P in the binary representation of n (putting as many leading zeros as there are leading zeros in P). If P consists only of zeros, one puts $$e_ P:=e_{1P}$$ (such a P is denoted by $$0^*)$$. Classical examples are the Thue-Morse sequence $$a_ 1$$ and the Rudin-Shapiro sequence $$a_{11}$$. (For basic results, connections with automata and further references see G. Christol, T. Kamae, M. Mendès-France and G. Rauzy [Bull. Soc. Math. Fr. 108, 401-419 (1980; Zbl 0472.10035)], J.-P. Allouche [Expo. Math. 5, 239-266 (1987; Zbl 0641.10041)].
Let o and u be the folding operations over and under on a rectangular piece of paper. A finite word w in o and u can be viewed as a folding instruction, reads from left to right, each successive instruction o or u being applied to the result of the previous folds. If the paper is unfold after performing the folding instruction, then it yields a sequence of upfolds (encoded by $$+1)$$ and downfolds (encoded by -1). This sequence of $$\pm 1's$$ is denoted by $$f_ w$$. For $$p\in \{o,u\}$$, the rule to get $$f_{wp}$$ from $$f_ w$$ is well-known (see below and for basic properties and references, see M. Dekking, M. Mendès-France and A. J. van der Poorten [Math. Intell. 4, 130-138, 173-181, 190- 196 (1982; Zbl 0493.10001, Zbl 0493.10002, Zbl 0493.10003)]. The paper under review is divided into four parts.
First part. The structure of pattern sequences $$a_ P$$ is determined. It follows by induction that for any binary pattern P of length $$d\geq 1$$ the sequence $$a(=a_ P)$$ verifies (Theorem 1) $(*)\quad a(n)X^ q_ n=a(k)X_ k^ q\quad if\quad n\equiv k\quad (mod 2^{d-1}),\quad n,k\geq 0,$ where $$X^ q_ n:=(a(n2^ q),a(n2^ q+1),...,a(n2^ q+2^ q-1))$$ is the n-th segment of length $$2^ q$$ of a. (For $$P=0^*$$ the values $$n=k=0$$ are excluded). Corollary: The sequence $$(X^ q_ n)_ n$$ is the product of the periodic sequence $$(a(n)X^ q_ n)_ n$$ of period $$2^{d-1}$$ with the original sequence a. Formula (*) generates the sequence a from its first $$2^ d$$ terms (corresponding to $$q=1)$$. For $$d\geq 2$$, the authors characterize the sequence $$a_ P$$ in terms of its 4-segments $$X_ k^ 2$$ (or $$Y_ k^ 2:=a(k)X_ k^ 2)$$. Theorem 3: $$X_ k^ 2$$ cannot belong to $$\{\pm (1,-1,-1,1), \pm (-1,1,-1,1)\}.$$ The periodic part of $$(Y^ 2_ n)_ n$$ is explicitly determined (Theorems 4, 5). All cases for $$d=2$$ and $$d=3$$ are explicitly given.
The second part is devoted to a generalization of property (*). Let G be an abelian group and let $$\Gamma$$ (G) be the group (with respect to term-wise operation) of sequences in G. Let $$X^ q_ n:=(a(nk^ q),a(nk^ q+1),...,a(nk^ q+k^ q-1))$$ be the sequence of $$k^ q$$- segments of a, where $$k\geq 1$$ and q,n$$\geq 0$$. Now G acts on $$k^ q$$- segments by operation on each term. Let $$\Gamma_ k(G)$$ be the subgroup of all sequences a in $$\Gamma$$ (G) satisfying $(**)\quad a^{- 1}(n)X^ q_ n=a^{-1}(m)X^ q_ m,\quad for\quad n\equiv m (mod M),$ for a fixed k, some modulus $$M=M(a,q)$$, and all m,n,q$$\geq 0$$. The modulus M(a,q) can be chosen as M(a,1) and if M and $$M'$$ are both allowable for M(a,q) (i.e., verify (**)), then so is $$(M,M')$$. Hence the least common divisor M(a) of all allowable modulus M(a,1) exists. The subgroup of a $$\in \Gamma_ k(G)$$ for which M(a) divides a power of k is denoted by $$\Lambda_ k(G).$$
Basic properties of $$\Gamma_ k(G)$$ (called k-th arithmetic fractal group of G) are given with a particular attention for $$G=\{\pm 1\}$$ and $$G={\mathbb{Z}}$$. Theorem 7: $$\Lambda_ k({\mathbb{Z}})$$ is generated by the constant sequences and the sequences $$e_ P$$, where P is any pattern of digits to base k with no leading zeros. Theorem 8 and Theorem 9: All relations among the generators $$e_ p$$ of $$\Lambda_ k({\mathbb{Z}})$$ follow from the relations $$e_ P(n)=\sum^{k-1}_{s=0}e_{sP}(n).$$
Application: Let $$c_ d$$ be the sequence self-generated by (**) with $$X_ 0^ d=I^{(d-1)}$$ (the string of length $$2^{d-1}$$ consisting of all ones) and $$X^ q_ 1=-X^ q_ 0$$ (q$$\geq d-1)$$. Then (Theorem 11): $$\prod_{P}a_ P=c_ d$$ where P runs over all binary patterns beginning with 1 and having length d. This part ends with the following amazing result (Theorem 12): Any sequence a of integers has a unique expansion $$a=a(0)+\sum_{P}r_ Pe_ P$$, $$r_ P\in {\mathbb{Z}}$$, where the sum runs over the patterns P base k (with no leading zeros).
Third part. Connection between pattern sequences and paper folding is studied. For $$p\in \{o,u\}$$ the folding operator $$F_ p$$ can be defined for any string $$x=(x_ 0,x_ 1,...,x_ n)$$, $$x_ i\in \{\pm 1\}$$ by $F_ p(x):=(\epsilon (p),x_ 0,-\epsilon (p),x_ 1,...,(- 1)^ n\epsilon (p),x_ n,(-1)^{n+1}\epsilon (p))$ where $$\epsilon (p)=+1$$ if $$p=o$$ and -1 if $$p=u$$. $$F_ p$$ is easily extended to infinite strings. For the empty string $$\wedge:=( )$$ one puts $$F_ p(\wedge):=\epsilon (p)$$. For any word $$w:=p_ 1...p_ m$$ in the letters o and u one has $$f_ w:=F_{p_ m}\circ...\circ F_{p_ 1}(\wedge)$$. Now, for any finite or infinite sequence f of $$\pm 1's$$, are the sum sequence s and the direction sequence d defined by $$s(n)=\sum^{n}_{j=1}f_ w(j)$$, $$(s(0):=0)$$ and $$d(n):=i^{s(n)}\delta_ n$$ where $$\delta_ n:=1$$ if n is even, -i otherwise. For $$f=f_ w$$, the direction sequence is denoted by $$d_ w$$; it is a string of $$\pm 1's$$ of length $$2^ m-1$$ if m is the length of w. For words $$w=\alpha \beta,w'=\alpha '\beta$$ which end with the same word $$\beta$$, the strings $$f_ w,f_{w'}$$ begin (from the left) with the same string, namely $$f_{\beta}$$. Let E be the set of all finite or infinite strings of $$\pm 1's$$ endowed with the compact topology of the coordinatewise convergence. To the sequence of folding instructions given by $$W_ m:=w_ 0(w_ 1)^ m$$ corresponds a paper folding sequence $$(f_{W_ m})_ m$$ which converges in E to a unique infinite paper folding sequence f. Clearly, this sequence does not depend on $$w_ 0$$. Theorem 13 says more: $$s\in \Gamma_{2^{\lambda}}({\mathbb{Z}})$$ and $$d\in \Gamma_{2^{\lambda}}(\pm 1)$$ where $$\lambda$$ is the length of the periodic part $$w_ 1$$. It follows (Corollary 2) that s is a linear combination of sequences $$e_ P$$ base $$2^{\lambda}$$ and d is a finite product of pattern sequences $$a_ P$$ base $$2^{\lambda}$$. Theorem 14 determines all the possible 4-segments of any direction sequence d. The last part of this section gives a simple arithmetic proof of the following result (Theorem 15): The only binary pattern sequences which are direction sequences are $$a_{01}(=d_{(u)^{\infty}})$$, $$a_{10}(=d_{(o)^{\infty}})$$ and $$a_{11}(=d_{(uo)^{\infty}}).$$
Fourth part. All direction sequences which belong to $$\Gamma_{2^{\lambda}}(\pm 1)$$ are determined. For any infinite string $$w=w_ 0w_ 1w_ 2..$$. in o and u one associates the reverse sequence $$\omega:=...w_ 2w_ 1w_ 0$$. The sequence $$(d_{w_ nw_{n- 1}...w_ 1w_ 0})_ n$$ converge to an infinite direction sequence $$d_{\omega}$$. Theorem 19: $$d_{\omega}\in \Gamma_{2\lambda}(\pm 1)$$ for some $$\lambda$$ if and only if $$d_{\omega}$$ is a finite product of pattern sequences base $$2^{\lambda}$$ and this property holds if and only if $$\omega =(w_ 1)^{\infty}w_ 0$$ where $$w_ 1$$ has length $$\lambda$$ or $$w_ 1=\bar w_ 2w_ 2$$ where $$w_ 2$$ has length $$\lambda$$ and $$\bar w_ 2$$ is obtained from $$w_ 2$$ by interchanging o and u (see also M. Mendès-France and J. O. Shallit [J. Comb. Theory, Ser. A 50, No.1, 1-23 (1989; Zbl 0663.10056)]). The proof introduces a dynamical system ($${\mathcal D}_ w,\tau)$$ associated with the infinite string w. Here, $${\mathcal D}_ w$$ is the compact subset of $$\{\pm 1\}^{{\mathbb{N}}}$$ given by all limit points in E of the sequence $$(d_{w_ 0w_ 1...w_ n})_ n$$. The map $$\tau$$ defined on $${\mathcal D}_ w$$ by $$\tau (d_{\omega})=d_{\omega '}$$, where $$\omega =\omega 'p$$ $$(p=o$$ or u), is continuous, surjective and moreover (Theorem 17 and Theorem 18) the following properties for any directional sequence $$d=d_{\omega}$$ are equivalent: (i) $$d\in \Gamma_{2^{\lambda}}(\pm 1)$$, (ii) $$a=d(\tau^{\lambda}(d))$$ is periodic (and M(a) is the smallest even period of a), (iii) the orbit of d under $$\tau$$ is finite.
This paper is easy to follow, self-contained and the most part is elementary. Some useful algebraic combinatorial laws on sequences are introduced to exhibit self-generating and self-similar properties of the elements of $$\Gamma_ k(G)$$. Several interesting worked examples illustrate definitions and results.
Reviewer: P.Liardet

### MSC:

 11A63 Radix representation; digital problems 11B99 Sequences and sets 11A99 Elementary number theory
Full Text: