Canonical positions for the factors in paperfolding sequences (Q1329729)

A paper-folding sequence, \(u(n)\), is obtained by repeatedly folding a piece of paper in half according to a sequence of folding instructions (left half over right or right over left). If the paper is unfolded, the terms of the sequence can be seen to be \(u(n) =0\) or 1 according as the fold goes down or up. Recursively, \(u(4n +1)=0\) (respectively 1), \(u(4n+ 3)=1\) (respectively 0) and \(u(2n)\) is again a paper-folding sequence. A factor of length \(k\) is a word \(u(n) u(n+1) \dots u(n+k -1)\). The complexity \(P_ u (k)\) is the number of factors of length \(k\) in the sequence \(u\). \textit{J.-P. Allouche} [Bull. Aust. Math. Soc. 46, No. 1, 23- 32 (1992; Zbl 0753.11011)] proved that \(P_ u(k)= 4k\) for \(k\geq 7\). In this paper, a uniformising set \({\mathcal P}_ k\) of integers of cardinality \(4k\) is constructed with the property that the factors of length \(k\) of any paper-folding sequence are just the factors beginning at the places indexed by the integers of \({\mathcal P}_ k\). A minimal sequence is one such that for every integer \(n\geq 1\) there is an integer \(r\) with the property that every factor of length \(r\) contains all the factors of length \(n\). The smallest such \(r\), denoted \(R_ u (n)\), is called the recurrence function of the sequence \(u\). The paper- folding sequences are minimal and their recurrence function satisfies \(r_ u (k)< 44k\). All this and some more properties of the language of all factors of paper-folding sequences are studied by means of explicit 2-automatic constructions.