An Irrationality Measure for Regular Paperfolding Numbers

Michael Coons Department of Pure Mathematics University of Waterloo 200 University Avenue West Waterloo, Ontario N2L 6P1 Canada

               mcoons@math.uwaterloo.ca

Paul Vrbik Department of Computer Science University of Western Ontario 1151 Richmond Street North London, Ontario N6A 5B7 Canada

                   pvrbik@csd.uwo.ca

In memory of Alf van der Poorten

Abstract

Let F(z) = ∑_{n⩾1} f_{n}z^{n} be the generating series of the regular paperfolding sequence. For a real number α the irrationality exponent μ(α), of α, is defined as the supremum of the set of real numbers μ such that the inequality |α − p/q| < q^{−μ} has infinitely many solutions (p, q) ∈ ℤ × ℕ. In this paper, using a method introduced by Bugeaud, we prove that

μ(F(1/b)) ⩽ \frac{275331112987}{137522851840} = 2.002075359 ⋯

for all integers b ⩾ 2. This improves upon the previous bound of μ(F(1/b)) ⩽ 5 given by Adamczewski and Rivoal.

1 A tale unfolded, and unfolded, and unfolded, and …

We consider a piece of paper, and choose and edge. We fold the paper in half towards the chosen edge, then we fold it in half again towards the chosen edge, and repeat the process indefinitely. Unfolding the paper, we are left with a sequence of ridges and valleys. Assign to each ridge the value 0, and to each valley the value 1. Such a sequence of 0s and 1s is called a paperfolding sequence.

Now, suppose that the paper was horizontal to start out with and consider the two possible folds, say “up” (which we call an up–fold) and “down” (which we call a down–fold), as indicated in Figure 1.

[figure: up–fold; down–fold]

Figure 1: Orientations of up– and down–folds.

In general, there is no reason to prefer one fold choice over the other, but some choices are more traditional than others and have attracted more interest.

The most traditional choice made by paperfolders is to choose the up–fold only; the resulting sequence of 0s and 1s is called the regular paperfolding sequence, which we will denote by f := {f_{n}}_{n⩾1}. The sequence starts

f = {1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, …}.

Denote by F(z) the generating series of the regular paperfolding sequence f = {f_{n}}_{n⩾1}; that is,

F(z) := ∑_{n⩾1}f_{n}z^{n}.

Note that F(z) converges in the region |z| < 1. Now let b ⩾ 2 be an integer. We refer to the numbers F(1/b) as regular paperfolding numbers.

It turns out that the regular paperfolding sequence can be produced by a finite automaton; in particular f is 2-automatic and is produced by the automaton in Figure 2. Numbers that can be produced by finite automata are very simple from the point of view of computational complexity, and as such the arithmetical properties of automatic numbers are of great interest; see [4] for more details and specific definitions regarding automatic sequences and [1, 2] for Diophantine properties related to automatic numbers.

Let ξ be a real number. The irrationality exponent μ(ξ), of the real number ξ, is defined as the supremum of set of real numbers μ such that the inequality

|ξ − \frac{p}{q}| < \frac{1}{q^{μ}}

has infinitely many solutions (p, q) ∈ ℤ × ℕ.

              [figure: 1; 1; 0; 0; 0; 1; 1; 1; 0; 0; 1; 0]

Figure 2: The generating 2–automaton of the regular paperfolding sequence.

In 2009, Adamczewski and Rivoal [3] showed that μ(F(1/b)) ⩽ 5 for each integer b ⩾ 2. The main result of this paper is to improve upon their result. In particular, we prove that

Theorem 1. For all integers b ⩾ 2 we have

μ (F (1/b)) ⩽ \frac{275331112987}{137522851840} = 2.002075359 · · · .

Our proof of Theorem 1 will mostly follow the method outlined by Bugeaud in [6], but with the use of a computation. The steps are as follows: get a useful rational function approximation to F(z), exploit a functional equation satisfied by F(z) to make this approximation even more useful, and then turn these functional rational approximations into true rational approximations to the number F(1/b). This method can be thought of as using ideas of Mahler’s method in transcendence theory piggy–backed onto Padé’s approximation theory. Combining this with a computation, we are able to yield the desired result.

2 Useful observations

In this section, we highlight some useful facts about the regular paperfolding sequence; see [7, 8, 9, 11, 12, 13] for details and further information on paperfolding sequences.

The regular paperfolding sequence f = {f_{n}}_{n⩾1} satisfies for all n ⩾ 0 the recurrences

f_{4n+1} = 1,  f_{4n+3} = 0,  and f_{2(n+1)} = f_{(n+1)}.

Viewing the regular paperfolding sequence in the light of these recurrences proves extremely useful for our purposes as they are equivalent to the generating series F(z) satisfying the Mahler–type functional equation

F(z^{2}) = F(z) − \frac{z}{1 − z^{4}} .  (1)

By applying (1) multiple times, for all m ⩾ 1 we have that

F(z^{2^{m}}) = F(z) − ∑_{j=0}^{m−1} \frac{z^{2^{j}}}{1 − z^{2^{j+2}}} .  (2)

3 Hankel determinants and rational approximations

To apply Bugeaud’s method, we require several definitions and lemmas.

Let a = {a_{n}}_{n⩾1}. The n–th Hankel matrix H_{n}^{1}(a) of the sequence a is the n × n matrix

H_{n}^{1}(a) := (a_{i+j−1})_{1⩽i,j⩽n}.

The n–th Hankel determinant is denoted det H_{n}^{1}(a).

Given an analytic function G(z), the rational function R(x), whose numerator has degree bounded by m and denominator has degree bounded by n, is the [m/n]_{G} Padé approximant to G(z) provided

G(z) − R(z) = O(z^{m+n+1}).

Connecting Hankel determinants to Padé approximants, we will use the following lemma; see [5, Page 35] (as stated this is not verbatim the result cited; it is the version of the result for sequences starting at n = 1 as opposed to sequences starting at n = 0).

Lemma 2 (Brezinski [5]). Let c = {c_{n}}_{n⩾1} and C(z) = ∑_{n⩾1} c_{n}z^{n} ∈ ℤ[[z]] with |z| < 1. If det H_{k}^{1}(c) ≠ 0, then the [k/k]_{C} Padé approximant exists and satisfies

C(z) − [k/k]_{C} = \frac{det H_{k+1}^{1}(c)}{det H_{k}^{1}(c)}z^{2k+1} + O(z^{2k+2}).

We require the following two lemmas, the first is a result of Adamczewski and Rivoal [3, Lemma 4.1] and the second is a slight, though extremely necessary, modification of Lemma 2 of [6] (we have included its proof for completeness).

Lemma 3 (Adamczewski and Rivoal [3]). Let ξ, δ, ρ and ϑ be real numbers such that 0 < δ ⩽ ρ and ϑ ⩾ 1. Let us assume that there exists a sequence {p_{n}/q_{n}}_{n⩾1} of rational numbers and some positive constants c_{0}, c_{1} and c_{2} such that both

q_{n} < q_{n+1} ⩽ c_{0}q_{n}^{ϑ},

and

\frac{c_{1}}{q_{n}^{1+ρ}} ⩽ |ξ − \frac{p_{n}}{q_{n}} | ⩽ \frac{c_{2}}{q_{n}^{1+δ}} .

Then we have that

μ(ξ) ⩽ (1 + ρ)\frac{ϑ}{δ}.

Lemma 4. Let K ⩾ 1 and n_{0} be positive integers. Let {a_{j}}_{j⩾1} be the increasing sequence of integers composed of all the numbers of the form k2^{n}, where n ⩾ n_{0} and k ranges over all the odd integers in [2^{K−1} + 1, 2^{K} + 1]. Then

a_{j+1} ⩽ (\frac{2^{K−1} + 3}{2^{K−1} + 1}) a_{j}.

Proof. Let n be large enough and consider the increasing sequence {a_{j}}_{j⩾1} of all integers of the form k2^{n} where k is an odd number in [2^{K−1} + 1, 2^{K} + 1]. Note that for a given j we have that for some m and some odd number a with 1 ⩽ a ⩽ 2^{K−1} + 1 we have a_{j} = 2^{m}(2^{K−1} + a). We consider two cases.

If a < 2^{K−1} + 1, then a_{j+1} ⩽ 2^{m}(2^{K−1} + a + 2), so that

\frac{a_{j+1}}{a_{j}} ⩽ \frac{2^{K−1} + a + 2}{2^{K−1} + a} ⩽ \frac{2^{K−1} + 3}{2^{K−1} + 1}.

If a = 2^{K−1} + 1, then a_{j+1} ⩽ 2^{m+1}(2^{K−1} + 1) = 2^{m}(2^{K} + 2), so that

\frac{a_{j+1}}{a_{j}} ⩽ \frac{2^{K} + 2}{2^{K} + 1} ⩽ \frac{2^{K−1} + 3}{2^{K−1} + 1}.

This proves the lemma.

In order to use Lemma 2, we give the following computational result.

Lemma 5. For all k ⩽ 2^{13} + 3 we have that det H_{k}^{1}(f) ≠ 0.

Lemma 5 is provided by a computation; see Appendix A for the C++ program written for this lemma. The computation was parallelized in a trivial manner: node i ∈ [1, P] calculates the determinants of H_{P ·j+i}^{1}(f) for j = 1, …, N and N as large as possible. The implementation uses the GNU Scientific Library [10], particularly those commands that do LU-decomposition and determinants on matrices of massive size. (Doing an LU-decomposition—in place— before the determinant calculation improves the calculation.)

This result allows us apply Lemma 4 with K = 13. One would like to show that all such determinants are nonzero, but this seems a daunting task at the moment, though in the future one may be more determined; see the section on Concluding Remarks for further discussion on this topic.

4 Proof of the main result

Proof of Theorem 1. Throughout this proof we will assume that |z| < 1 so that our big-O terms have meaning.

By Lemma 2 and Lemma 5, for all k ⩽ 2^{13} + 3 there exist polynomials P_{k,0}(z), Q_{k,0}(z) ∈ ℤ[z], with

deg P_{k,0}(z) ⩽ k and deg Q_{k,0}(z) ⩽ k,

and a nonzero h_{k} ∈ ℚ such that

F(z) − \frac{P_{k,0}(z)}{Q_{k,0}(z)} = h_{k}z^{2k+1} + O(z^{2k+2}).

Thus, sending z ↦ z^{2^{m}} we have that

F(z^{2^{m}}) − \frac{P_{k,0}(z^{2^{m}})}{Q_{k,0}(z^{2^{m}})} = h_{k}z^{2^{m}(2k+1)} + O(z^{2^{m}(2k+2)}),

and using the functional equation (2) for F(z) it follows that

F(z) − ∑_{j=0}^{m−1} \frac{z^{2^{j}}}{1 − z^{2^{j+2}}} − \frac{P_{k,0}(z^{2^{m}})}{Q_{k,0}(z^{2^{m}})} = h_{k}z^{2^{m}(2k+1)} + O(z^{2^{m}(2k+2)}).

Define P_{k,m}(z) and Q_{k,m}(z) by

\frac{P_{k,m}(z)}{Q_{k,m}(z)} := ∑_{j=0}^{m−1} \frac{z^{2^{j}}}{1 − z^{2^{j+2}}} + \frac{P_{k,0}(z^{2^{m}})}{Q_{k,0}(z^{2^{m}})},

so that

F(z) − \frac{P_{k,m}(z)}{Q_{k,m}(z)} = h_{k}z^{2^{m}(2k+1)} + O(z^{2^{m}(2k+2)}).

Let b ⩾ 2 be an integer and z = 1/b; for ε > 0, we have for large enough m, say m ⩾ m_{0}(k), that

(1 − ε)h_{k}b^{−2^{m}(2k+1)} ⩽ |F(1/b) − \frac{P_{k,m}(1/b)}{Q_{k,m}(1/b)}| ⩽ (1 + ε)h_{k}b^{−2^{m}(2k+1)}.

It remains to determine the degree of P_{k,m}(z) and Q_{k,m}(z). To this end, note that writing

\frac{P_{m}(z)}{Q_{m}(z)} = ∑_{j=0}^{m−1} \frac{z^{2^{j}}}{1 − z^{2^{j+2}}} ,

we have that

deg Q_{m}(z) ⩽ deg(1 − z^{2^{m+1}}) = 2^{m+1}

and that

deg P_{m}(z) ⩽ max_{0⩽j⩽m−1} \{\frac{z^{2^{j}}(1 − z^{2^{m+1}})}{1 − z^{2^{j+2}}}\}

= max_{0⩽j⩽m−1}{2^{m+1} − 2^{j+2} − 2^{j}}

= 2^{m+1} − 5 ⩽ 2^{m+1}.

Using the definitions of P_{m}(z) and Q_{m}(z),

deg Q_{k,m}(z) = deg Q_{m}(z)Q_{k,0}(z^{2^{m}}) = deg Q_{m}(z) + deg Q_{k,0}(z^{2^{m}}) < 2^{m}(k + 2),

and

deg P_{k,m}(z) = max{deg P_{m}(z)Q_{k,0}(z^{2^{m}}), P_{k,0}(z^{2^{m}})} < 2^{m}(k + 2).

We continue following Bugeaud [6] by defining the integers

p_{k,m} := b^{2^{m}(k+2)}P_{k,m}(1/b)

and

q_{k,m} := b^{2^{m}(k+2)}Q_{k,m}(1/b).

Since h_{k} is nonzero there exist positive real constants c_{i}(k) (i = 1, …, 4) depending only on k so that

c_{1}(k)b^{2^{m}(k+2)} ⩽ q_{k,m} ⩽ c_{2}(k)b^{2^{m}(k+2)},  (3)

and

\frac{c_{3}(k)}{b^{2^{m+1}(k+1/2)}} ⩽ |F(1/b) − \frac{p_{k,m}}{q_{k,m}} | ⩽ \frac{c_{4}(k)}{b^{2^{m+1}(k+1/2)}} .  (4)

Note that

2^{m}(k + 2) = 2^{m}(k + 1/2) (\frac{k + 2}{k + 1/2}) ,

so that by (3) there are positive constants c_{5}(k) and c_{6}(k) such that

\frac{c_{5}(k)}{q_{k,m}^{2· \frac{k+1/2}{k+2}}} ⩽ \frac{1}{b^{2^{m+1}(k+1/2)}} ⩽ \frac{c_{6}(k)}{q_{k,m}^{2· \frac{k+1/2}{k+2}}} .

Applying this to (4) yields

\frac{c_{3}(k)c_{5}(k)}{q_{k,m}^{1+ \frac{k−1}{k+2}}} ⩽ |F(1/b) − \frac{p_{k,m}}{q_{k,m}} | ⩽ \frac{c_{4}(k)c_{6}(k)}{q_{k,m}^{1+ \frac{k−1}{k+2}}}.  (5)

Let K ⩾ 3 be an integer and denote by m_{1}(k) an integer such that the sequence {q_{k−2,m}}_{m⩾m_{1}(k)} is increasing. We define the sequence of positive integers {Q_{K,n}}_{n⩾1} as the sequence of all the integers q_{k−2,m} with k odd, 2^{K−1} − 1 ⩽ k ⩽ 2^{K} − 1, m ⩾ m_{1}(k), put in increasing order. Thus by (3), (5), and Lemma 4, there exist positive constants C_{1}(K), C_{2}(K) and C_{3}(K) such that both

Q_{K,n} < Q_{K,n+1} ⩽ C_{1}(K) · QK,n^{\frac{2^{K−1}+3}{2^{K−1}+1}}

and

\frac{C_{2}(K)}{Q_{K,n}^{1+ \frac{2^{K}}{2^{K} +3}}} ⩽ |F(1/b) − \frac{P_{K,n}}{Q_{K,n}} | ⩽ \frac{C_{3}(K)}{Q_{K,n}^{1+ \frac{2^{K−1}}{2^{K−1}+3}}} ,

where we have chosen the P_{K,n} as the p_{k,m} that corresponds with the identity Q_{K,n} = q_{k,m}. Applying Lemma 3 with ρ = \frac{2^{K}}{2^{K}+3}, δ = \frac{2^{K−1}}{2^{K−1}+3} and ϑ(K) = \frac{2^{K−1}+3}{2^{K−1}+1}, we have that

μ(F(1/b)) ⩽ \frac{(2^{K+1} + 3)(2^{K−1} + 3)^{2}}{(2^{K−1} + 1)(2^{K} + 3)2^{K−1}} .  (6)

Since we may take K up to 13, we have that

μ(F(1/b)) ⩽ \frac{275331112987}{137522851840} = 2.002075359 ⋯

for all b ⩾ 2. This proves the theorem.

5 Concluding remarks

Note that using (6), the larger the available K the better your bound. Thus (6) provides the following immediate corollary.

Corollary 6. If det H_{k}^{1}(f) ≠ 0 for all k, then μ(F(1/b)) = 2 for all integers b ⩾ 2.

While the proof of the assumption in the previous corollary is not in hand, computational evidence lends some credence. Indeed, using some simple computations we are led to believe that the sequence {det H_{n}^{1}(f)}_{n⩾1} satisfies some nice properties. One such property that could be conjectured is that if one writes |H_{n}^{1}(f)| for the determinant modulo 2, we have

∑_{n⩾1}|H_{n}^{1}(f)|z^{n} = \frac{z + z^{2} + z^{5} + z^{8} + z^{9} + z^{10}}{1 − z^{10}} ;

that is, the sequence {|H_{n}^{1}(f)}_{n⩾1} is periodic with period 10 and 6 out of every 10 values is odd.

6 Acknowledgements

The first author thanks Yann Bugeaud for introducing him to this beautiful topic and for providing a copy of his preprint [6]. Both authors thank the anonymous referee for valuable comments which improved the exposition of this paper.

A C++ program used for Lemma 5

#include <iomanip>
#include <fstream>
#include <iostream>
#include <sys / time . h>
#include <g s l / g s l m a t r i x f l o a t . h>
#include <g s l / gsl permutation . h>
#include <g s l / g s l l i n a l g . h>
using namespace std ;
int as ( int n) {
// generate paper f o l d i n g sequence
i f (n % 4 = 1) {
return 1 ;
} else i f (n % 4 = 3){
return 0 ;
} else {
return as (n / 2 ) ;
}

}

int main ( int argc , char ∗ argv [ ] ) {
int n ;
ofstream o u t f ( argv [ 1 ] ) ;
for (n=8555; n>0; n+=2) {
// c r e a t e an n x n matrix
g s l m a t r i x ∗ gslMatrix = g s l m a t r i x a l l o c (n , n ) ;
// f i l l matrix
for ( int i = 0 ; i < n ; i++) {
for ( int j = 0 ; j < n ; j++) {
g s l m a t r i x s e t ( gslMatrix , i , j , as ( i+1+j ) ) ;
}

}

int s i g n = 0 ;
gsl permutation ∗perm = g s l p e r m u t a t i o n a l l o c (n ) ;
gsl linalg LU decomp ( gslMatrix , perm , &s i g n ) ;
int r e s ;
// t e s t f o r zero−determinant
i f ( g s l l i n a l g L U d e t ( gslMatrix , s i g n )==0) {
r e s = 1 ;
} else {
r e s = 0 ;

};

g s l m a t r i x f r e e ( gslMatrix ) ;
g s l p e r m u t a t i o n f r e e ( perm ) ;

}

return 0 ;

}

References

[1] B. Adamczewski and Y. Bugeaud, On the complexity of algebraic numbers. I. Expansions in integer bases, Ann. of Math. (2) 165 (2007), 547–565.

[2] B. Adamczewski and J. Cassaigne, Diophantine properties of real numbers generated by finite automata, Compos. Math. 142 (2006), 1351–1372.

[3] B. Adamczewski and T. Rivoal, Irrationality measures for some automatic real numbers, Math. Proc. Cambridge Philos. Soc. 147 (2009), 659–678.

[4] J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge University Press, Cambridge, 2003.

[5] C. Brezinski, Padé-type Approximation and General Orthogonal Polynomials, International Series of Numerical Mathematics, Vol. 50, Birkhäuser Verlag, 1980.

[6] Y. Bugeaud, On the rational approximation of the Thue–Morse–Mahler number, Ann. Inst. Fourier (Grenoble), to appear.

[7] M. Dekking, M. Mendès France, and A. van der Poorten, Folds, Math. Intelligencer 4 (1982), 130–138.

[8] M. Dekking, M. Mendès France, and A. van der Poorten, Folds. II. Symmetry disturbed, Math. Intelligencer 4 (1982), 173–181.

[9] M. Dekking, M. Mendès France, and A. van der Poorten, Folds. III. More morphisms, Math. Intelligencer 4 (1982), 190–195.

[10] M. Galassi et al., GNU Scientific Library Reference Manual, 3rd ed., 2011.

[11] M. Mendès France, Paper folding, space-filling curves and Rudin-Shapiro sequences, Papers in Algebra, Analysis and Statistics (Hobart, 1981), Contemp. Math., Vol. 9, Amer. Math. Soc., 1981, pp. 85–95.

[12] M. Mendès France and A. van der Poorten, Arithmetic and analytic properties of paper folding sequences, Bull. Austral. Math. Soc. 24 (1981), 123–131.

[13] P. Morton, Connections between binary patterns and paperfolding, Sém. Théor. Nombres Bordeaux (2) 2 (1990), 1–12.

2010 Mathematics Subject Classification: Primary 11J82; Secondary 11B37, 41A21. Keywords: Irrationality measure, Padé approximant, Hankel determinant, paperfolding sequence.

(Concerned with sequence \underline{A014577}.)

Received September 14 2011; revised version received December 14 2011. Published in Journal of Integer Sequences, December 27 2011.

Return to Journal of Integer Sequences home page.