Irrationality of Growth Constants Associated with Polynomial Recursions

Stephan Wagner^{1} Department of Mathematics

Uppsala University Box 480 751 06 Uppsala Sweden

stephan.wagner@math.uu.se

and

Department of Mathematical Sciences

Stellenbosch University Private Bag X1 Matieland 7602 South Africa

   swagner@sun.ac.za

Volker Ziegler^{2} Department of Mathematics

University of Salzburg Hellbrunnerstrasse 34/I

5020 Salzburg Austria

volker.ziegler@sbg.ac.at

Abstract

We consider integer sequences that satisfy a recursion of the form x_{n+1} = P (x_{n}) for some polynomial P of degree d > 1. If such a sequence tends to infinity, then it satisfies an asymptotic formula of the form x_{n} ∼ Aα^{d^{n}}, but little can be said about the constant α. In this paper, we show that α is always irrational or an integer. In fact, we prove a stronger statement: if a sequence (G_{n})_{n≥0} satisfies an asymptotic formula of the form G_{n} = Aα^{n} + B + O(α^{−ϵn}), where A, B are algebraic and α > 1, and the sequence contains infinitely many integers, then α is irrational or an integer.

1Supported by the Knut and Alice Wallenberg Foundation.

2Supported by the Austrian Science Fund (FWF) under the project I4406.

1 Introduction

Integer sequences obtained by polynomial iteration, i.e., sequences that satisfy a recursion of the form

x_{n+1} = P (x_{n}),

occur in several areas of mathematics. One can find many interesting examples in Finch’s book on mathematical constants [2, Chapter 6.10].

Let us give two concrete examples: the first is the sequence given by x_{0} = 0 and x_{n+1} = x_{n}^{2} + 1 for n ≥ 0, which is entry \underline{A003095} in the On-Line Encyclopedia of Integer Sequences (OEIS) [6]. Among other things, x_{n} is the number of binary trees whose height (greatest distance from the root to a leaf) is less than n. This sequence grows very rapidly: there exists a constant β ≈ 1.2259024435 (the digits are \underline{A076949} in the OEIS) such that x_{n} = ⌊β^{2^{n}}⌋. However, this formula is not as explicit as it may seem, since the only known way to evaluate the constant β numerically involves all elements of the sequence: it can be expressed as

β = ∏_{n=1}^{∞} (1 + x_{n}^{−2})^{2^{−n−1}}.

Another well-known example is Sylvester’s sequence (\underline{A000058} in the OEIS), which is given by y_{0} = 2 and y_{n+1} = y_{n}^{2} − y_{n} + 1. It arises in the context of Egyptian fractions, y_{n} being the smallest positive integer for each n such that

\frac{1}{y_{0}} + \frac{1}{y_{1}} + \frac{1}{y_{2}} + ⋯ + \frac{1}{y_{n}} < 1.

There is also a pseudo-explicit formula for this sequence: for a constant γ ≈ 1.5979102180, we have y_{n} = ⌊γ^{2^{n}} + \frac{1}{2}⌋. However, again no formula for γ is known that does not involve the sequence elements. This is also the reason why little is known about the constants β and γ in these two examples and generally growth constants associated with similar sequences that satisfy a polynomial recursion.

In this short note, we will prove that the constants β and γ in these examples are— perhaps unsurprisingly—irrational, as are all non-integer growth constants associated with similar sequences that follow a polynomial recursion. The precise statement reads as follows:

Theorem 1. Suppose that an integer sequence satisfies a recursion of the form x_{n+1} = P (x_{n}) for some polynomial P of degree d > 1 with rational coefficients. Assume further that x_{n} → ∞ as n → ∞. Set

α = lim_{n→∞}(x_{n})^{d^{−n}}.

Then α is a real number greater than 1 that is either irrational or an integer.

It is natural to conjecture that the constants β and γ in our first two examples are not only irrational, but even transcendental. This is not always true for polynomial recursions in general, though: for example, consider the sequence given by z_{1} = 3 and z_{n+1} = z_{n}^{2} − 2. It is not difficult to prove that

z_{n} = L_{2^{n}} = (\frac{1 + \sqrt{5}}{2})^{2^{n}} + (\frac{1 − \sqrt{5}}{2})^{2^{n}}

for all n ≥ 1, where L_{n} denotes the n-th Lucas number. Thus the constant α in Theorem 1 would be the golden ratio in this example.

In the following section, we briefly review the classical method to determine the asymptotic behavior of polynomially recurrent sequences. Theorem 1 will follow as a consequence of a somewhat stronger result, Theorem 2. This theorem and its proof, which makes use of the subspace theorem, will be given in Section 3.

2 Asymptotic formulas for polynomially recurrent sequences

There is a classical technique for the analysis of polynomial recursions. The 1973 paper of Aho and Sloane [1] already contains a treatment of the two examples given in the introduction (along with many other examples). See also the book of Greene and Knuth [3, Chapter 2.2.3] for a discussion of the method.

Let the polynomial P in the recursion x_{n+1} = P (x_{n}) be given by

P (x) = c_{d}x^{d} + c_{d−1}x^{d−1} + ⋯ + c_{0}.

Note that

P (x) = c_{d}(x + \frac{c_{d−1}}{dc_{d}} )^{d} + O(x^{d−2}).

So if we perform the substitution y_{n} = c_{d}^{1/(d−1)}(x_{n} + \frac{c_{d−1}}{dc_{d}}), the recursion becomes

y_{n+1} = c_{d}^{1/(d−1)}(P (x_{n}) + \frac{c_{d−1}}{dc_{d}} )

= c_{d}^{d/(d−1)}(x_{n} + \frac{c_{d−1}}{dc_{d}} )^{d} + O(x_{n}^{d−2})

= y_{n}^{d} + O(y_{n}^{d−2}).

Let us assume that x_{n} → ∞, thus also y_{n} → ∞. It is easy to see that the sequences (x_{n})_{n≥0} and (y_{n})_{n≥0} are increasing from some point onwards in this case. We can also assume, without loss of generality, that none of the y_{n} is zero: if not, we simply choose a later starting point. Taking the logarithm, we obtain

log y_{n+1} = d log y_{n} + O(y_{n}^{−2})

or equivalently

log (\frac{y_{n+1}}{y_{n}^{d}} ) = O(y_{n}^{−2}).  (1)

Next express log y_{n} as follows:

log y_{n} = d log y_{n−1} + log (\frac{y_{n}}{y_{n−1}^{d}} ) = d^{2} log y_{n−2} + d log (\frac{y_{n−1}}{y_{n−2}^{d}} ) + log (\frac{y_{n}}{y_{n−1}^{d}} )

= ⋯ = d^{n} log y_{0} + ∑_{k=0}^{n−1} d^{n−k−1} log (\frac{y_{k+1}}{y_{k}^{d}} ).

Extending to an infinite sum (which converges since log(y_{k+1}/y_{k}^{d}) is bounded) yields

log y_{n} = d^{n}( log y_{0} + ∑_{k=0}^{∞} d^{−k−1} log (\frac{y_{k+1}}{y_{k}^{d}} )) − ∑_{k=n}^{∞} d^{n−k−1} log (\frac{y_{k+1}}{y_{k}^{d}} ).

Set

log α = log y_{0} + ∑_{k=0}^{∞} d^{−k−1} log (\frac{y_{k+1}}{y_{k}^{d}} ),

so that

log y_{n} = d^{n} log α − ∑_{k=n}^{∞} d^{n−k−1} log (\frac{y_{k+1}}{y_{k}^{d}} ).

In view of (1) and the fact that y_{n} ≤ y_{n+1} ≤ ⋯ for sufficiently large n, this gives

log y_{n} = d^{n} log α + O(y_{n}^{−2}),

and thus finally

y_{n} = α^{d^{n}} + O(α^{−d^{n}}).

This means that

x_{n} = c_{d}^{−1/(d−1)}α^{d^{n}} − \frac{c_{d−1}}{dc_{d}} + O(α^{−d^{n}}).

3 Application of the subspace theorem

We now combine the asymptotic formula from the previous section with an application of the subspace theorem to prove our main result on polynomial recursions. In fact, we first state and prove a somewhat stronger result that implies Theorem 1.

Theorem 2. Assume that the sequence (G_{n})_{n≥0} attains an integral value infinitely often, and that it satisfies an asymptotic formula of the form

G_{n} = Aα^{n} + B + O(α^{−ϵn}),

where α > 1, A and B are algebraic numbers with A ≠ 0, ϵ > 0, and the constant implied by the O-term does not depend on n. Then the number α is either irrational or an integer.

In order to prove the irrationality of α we make use of the following version of the subspace theorem, which is most suitable for our purposes, cf. [5, Chapter V, Theorem 1D].

Theorem 3 (Subspace theorem). Let K be an algebraic number field, let 𝔞_{K} be its maximal order, and let M(K) be the set of canonical absolute values of K. Moreover, let S ⊂ M(K) be a finite set of absolute values that contains all of the Archimedian ones. For each ν ∈ S, | · |_{ν} denotes the valuation corresponding to ν, and n_{ν} denotes the local degree. For x = (x_{1}, x_{2}, …, x_{N}) ∈ 𝔞_{K}^{N}, we define

\overline{|x|} = max_{{1≤i≤N \atop 1≤j≤deg K}} |x_{i}^{(j)}|,

the maximum being taken over all conjugates x_{i}^{(j)} of all entries x_{i} of x. Finally, for each ν ∈ S, let L_{ν,1}, …, L_{ν,N} be N linearly independent linear forms in n variables with coefficients in K. Then for given δ > 0, the solutions of the inequality

∏_{ν∈S} ∏_{i=1}^{N} |L_{ν,i}(x)|_{ν}^{n_{ν}} < \overline{|x|}^{−δ},

with x = (x_{1}, x_{2}, …, x_{N}) ∈ 𝔞_{K}^{N} and x ≠ 0, lie in finitely many proper subspaces of K^{N}.

Proof of Theorem 2. Let us assume contrary to the statement of Theorem 2 that α = p/q is rational, where p and q are coprime positive integers, p > q, and q ≠ 1. Moreover, assume that their prime factorizations are

p = p_{1}^{n_{1}} ⋯ p_{k}^{n_{k}} and q = q_{1}^{m_{1}} ⋯ q_{ℓ}^{m_{ℓ}}.

We choose K in the subspace theorem to be the normal closure of ℚ(A, B), and we write D = [K : ℚ]. We fix one embedding of K into ℂ, so that we can assume that K ⊆ ℂ. Moreover, let us write A and B as A = β_{1}/Q and B = β_{2}/Q, where β_{1} and β_{2} lie in the maximal order 𝔞_{K} of K, and Q is a positive integer such that the ideals (β_{1}, β_{2}) and (Q) are coprime.

If n is an index such that G_{n} is an integer, we deduce that there exists an algebraic integer a which may depend on n such that

G_{n} = \frac{β_{1}p^{n} + β_{2}q^{n} + a}{Qq^{n}} = Aα^{n} + B + \frac{a}{Qq^{n}} = Aα^{n} + B + O(α^{−ϵn}).

Since we are assuming that G_{n} is a rational integer, we can write the algebraic integer a in the form a = X − β_{1}p^{n} − β_{2}q^{n}, with X ∈ ℤ. Moreover, we know that

|a| < CQ (\frac{q^{1+ϵ}}{p^{ϵ}} )^{n} ,  (2)

where C is the constant implied by the O-term.

Assume that K has signature (r, s). We choose

S = {∞_{1}, …, ∞_{r+s}, 𝔭_{1,1}, …, 𝔭_{k,t_{k}}, 𝔮_{1,1}, …, 𝔮_{ℓ,u_{ℓ}}},

where the valuations 𝔭_{i,1}, …, 𝔭_{i,t_{i}} are all valuations lying above p_{i} for 1 ≤ i ≤ k, and the valuations 𝔮_{j,1}, …, 𝔮_{j,u_{j}} are all valuations lying above q_{j} for 1 ≤ j ≤ ℓ. Moreover, let

Gal(K/ℚ) = {σ_{1}, …, σ_{r}, σ_{r+1}, σ̄_{r+1}, …, σ_{r+s}, σ̄_{r+s}},

so that the valuation ∞_{i} is given by |x|_{∞_{i}} = |σ_{i}^{−1}x|, where | · | is the usual absolute value of ℂ. Finally, the conjugates of β_{1} and β_{2} are denoted by β_{j}^{(i)} = σ_{i}(β_{j}). We have the formula

|x_{1}β_{1}^{(i)} + x_{2}β_{2}^{(i)} + x_{3}|_{∞_{i}} = |x_{1}β_{1} + x_{2}β_{2} + x_{3}|

for arbitrary rational numbers x_{1}, x_{2}, x_{3}.

Next, we construct suitable linear forms to apply the subspace theorem. Let us write x_{1} = p^{n}, x_{2} = q^{n}, and x_{3} = a, thus N = 3. We choose our linear forms as L_{ν,1}(x) = x_{1}, L_{ν,2}(x) = x_{2} for all ν ∈ S, and L_{ν,3}(x) = x_{3} if ν lies above one of the valuations p_{1}, …, p_{k}. We choose L_{ν,3}(x) = β_{1}x_{1} + β_{2}x_{2} + x_{3} if ν lies above one of the valuations q_{1}, …, q_{ℓ}. Finally, if ν = ∞_{i}, then we put L_{∞_{i},3}(x) = (β_{1} − β_{1}^{(i)})x_{1} + (β_{2} − β_{2}^{(i)})x_{2} + x_{3}.

Using the product formula, cf. [4, pp. 99–100], and trivial estimates we obtain

∏_{ν∈S} |L_{ν,1}(x)|_{ν}^{n_{ν}} = 1,  ∏_{ν∈S} |L_{ν,2}(x)|_{ν}^{n_{ν}} = 1,
∏_{{ν|q_{j} \atop 1≤j≤ℓ}} |L_{ν,3}(x)|_{ν}^{n_{ν}} ≤ q^{−Dn},  ∏_{{ν|p_{i} \atop 1≤i≤k}} |L_{ν,3}(x)|_{ν}^{n_{ν}} ≤ 1.

Thus we are left to compute the quantities |L_{∞_{i},3}(x)|_{∞_{i}}. We obtain

|L_{∞_{i},3}(x)|_{∞_{i}} = |(β_{1} − β_{1}^{(i)})x_{1} + (β_{2} − β_{2}^{(i)})x_{2} + x_{3}|_{∞_{i}}
= |β_{1}p^{n} + β_{2}q^{n} + a − β_{1}^{(i)}p^{n} − β_{2}^{(i)}q^{n}|_{∞_{i}}
= |X − β_{1}^{(i)}p^{n} − β_{2}^{(i)}q^{n}|_{∞_{i}}
= |X − β_{1}p^{n} − β_{2}q^{n}| = |a|.

Combining all inequalities, we have

∏_{ν∈S} ∏_{i=1}^{3} |L_{ν,i}(x)|_{ν}^{n_{ν}} ≤ q^{−Dn}|a|^{D} < (CQ)^{D} (\frac{q}{p})^{ϵDn} .  (3)

Now choose δ > 0 small enough so that

(\frac{q}{p})^{ϵD} < p^{−δ}.

In view of (2), the inequality |a|_{ν} ≤ p^{n} holds for all valuations ν lying above ∞ for sufficiently large n, so that \overline{|x|} = |x_{1}| = p^{n}. Hence we obtain

(CQ)^{D} (\frac{q}{p})^{ϵDn} < (p^{n})^{−δ} = \overline{|x|}^{−δ}

for sufficiently large n. In view of (3), we have shown that

∏_{ν∈S} ∏_{i=1}^{n} |L_{ν,i}(x)|_{ν}^{n_{ν}} < \overline{|x|}^{−δ}.  (4)

By the subspace theorem, all solutions to (4) lie in finitely many subspaces of K^{3}. Since by assumption there are infinitely many solutions, there exists one subspace T ⊆ K^{3} which contains infinitely many solutions. Let T be defined by t_{1}x_{1} + t_{2}x_{2} + t_{3}x_{3} = 0, with fixed algebraic integers t_{1}, t_{2}, t_{3} ∈ 𝔞_{K}. Then there must be infinitely many integers n such that t_{1}p^{n} + t_{2}q^{n} + t_{3}a = 0, which is in contradiction to (2) and the assumption that p > q > 1. Thus we can conclude that α cannot be rational, unless q = 1 so that α is an integer.

Now the proof of Theorem 1 is straightforward.

Proof of Theorem 1. As derived in Section 2, if an integer sequence satisfies a recursion of the form x_{n+1} = P (x_{n}) for some polynomial P of degree d > 1 with rational coefficients, and x_{n} → ∞ as n → ∞, then an asymptotic formula of the form

x_{n} = Aα^{d^{n}} + B + O(α^{−d^{n}})

holds. If α is rational, but not an integer, then we have an immediate contradiction to Theorem 2.

4 Further generalizations

Let us remark that Theorem 2 can be extended to number fields:

Theorem 4. Let L be a number field, and let 𝔞_{L} be its maximal order. Assume that the sequence (G_{n})_{n≥0} attains values in O_{L} infinitely often, and that it satisfies an asymptotic formula of the form

G_{n} = Aα^{n} + B + O(|α|^{−ϵn}),

where |α| > 1, A and B are algebraic numbers with A ≠ 0, ϵ > 0, and the constant implied by the O-term does not depend on n. Then the number α is either an algebraic integer in 𝔞_{L}, or α ∉ L.

The proof of this theorem is similar to the proof of Theorem 2. In particular, let K be the normal closure of L(A, B), and assume that α = p/q with p ∈ 𝔞_{L} and q ∈ ℤ with q > 1. Then we consider the prime ideal factorizations

(p) = 𝔭_{1}^{n_{1}} ⋯ 𝔭_{k}^{n_{k}} and (q) = 𝔮_{1}^{m_{1}} ⋯ 𝔮_{ℓ}^{m_{ℓ}}

in K. We can construct the same linear forms as in the proof of Theorem 2 and use the subspace theorem to get a contradiction.

It is also possible to consider a higher-dimensional variant of Theorem 1. Let f_{1}, …, f_{N} ∈ ℤ[X_{1}, …, X_{N}] be polynomials of degree d > 1. Then we can consider a sequence (x_{n})_{n≥0} with x_{n} = (x_{n}^{(1)}, …, x_{n}^{(N)}) ∈ ℤ^{N} for all n ≥ 0 satisfying the polynomial recursion

x_{n+1} = f(x_{n}) = (f_{1}(x_{n}), …, f_{N}(x_{n})).

With this notation at hand we pose the following problem:

Problem 5. Assume that max {x_{n}^{(1)}, …, x_{n}^{(N)}} → ∞ as n → ∞, and let

α = lim_{n→∞} ( max {x_{n}^{(1)}, …, x_{n}^{(N)}} )^{d^{−n}}.

Is α necessarily irrational or an integer?

5 Acknowledgment

This paper resulted from an Erasmus+ staff exchange. Financial support from Erasmus+ EU funds is gratefully acknowledged.

References

[1] A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quart. 11 (1973), 429–437.

[2] Steven R. Finch, Mathematical Constants, Vol. 94 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, 2003.

[3] Daniel H. Greene and Donald E. Knuth, Mathematics for the Analysis of Algorithms, Vol. 1 of Progress in Computer Science and Applied Logic, Birkhäuser, third edition, 1990.

[4] Serge Lang, Algebraic Number Theory, Vol. 110 of Graduate Texts in Mathematics, Springer, second edition, 1994.

[5] Wolfgang M. Schmidt, Diophantine Approximations and Diophantine Equations, Vol. 1467 of Lecture Notes in Mathematics, Springer, 1991.

[6] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2020. Available

   at https://oeis.org.

2020 Mathematics Subject Classification: Primary 11J72; Secondary 11B37. Keywords: irrationality, polynomial recursion, growth constant.

(Concerned with sequences \underline{A000058}, \underline{A003095}, and \underline{A076949}.)

Received August 12 2020; revised versions received August 13 2020; December 31 2020; January 1 2021. Published in Journal of Integer Sequences, January 2 2021.

Return to Journal of Integer Sequences home page.