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.