Automated Proofs (or Disproofs) of Linear Recurrences Satisfied by Pisot Sequences

By Shalosh B. EKHAD, N. J. A. SLOANE, and Doron ZEILBERGER

Dedicated to Richard K. GUY on his one hundredth birthday

Abstract: Pisot sequences (sequences a_{n} with initial terms a_{0} = x, a_{1} = y, and defined for n > 1 by a_{n} = ⌊a_{n−1}^{2}/a_{n−2} + \frac{1}{2}⌋) often satisfy linear recurrences with constant coefficients that are valid for all n ≥ 0, but there are also cautionary examples where there is a linear recurrence that is valid for an initial range of values of n but fails to be satisfied beyond that point, providing further illustrations of Richard Guy’s celebrated “Strong Law of Small Numbers”. In this paper we present a decision algorithm, fully implemented in an accompanying Maple program (Pisot.txt), that first searches for a putative linear recurrence and then decides whether or not it holds for all values of n. We also explain why the failures happen (in some cases the ‘fake’ linear recurrence may be valid for thousands of terms). We conclude by defining, and studying, higher-order analogs of Pisot sequences, and point out that similar phenomena occur there, albeit far less frequently.

0. Maple Package and Sample Output

This article is accompanied by a Maple package, Pisot.txt, that is available, along with six input and output files, from

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/pisot.html .

1. Preface

Richard Guy famously formulated the Strong Law of Small Numbers, and in two classic articles [G1, G2] gave many examples of pairs of sequences that are equal for a certain number of initial terms, but eventually differ. Before him, around 1820 Charles Babbage [Ba] had already discussed numerous examples, and recalled how Fermat was misled by the numbers 2^{2^{n}} +1, and Euler [E] was almost led to believe that the central trinomial coefficients are the product of consecutive Fibonacci numbers.

But in all these examples, the sequences only agree for a moderate number of terms. As shown by David G. Cantor [C1, C2] and David Boyd [B1–B5] , the so-called Pisot sequences provide much more dramatic examples of Richard Guy’s Strong Law of Small Numbers. Here we find pairs of distinct sequences which agree for tens of thousands of terms. (Even more extreme examples arise from game theory–see for example entry A078608 in [OEIS], where there are two sequences which agree for all n from 1 to 777451915729367 but differ at 777451915729368.)

2. Pisot Sequences

We first recall the definition (cf. [Pi], [Ca], [B5]).

Definition: The Pisot sequence with index r, E_{r}(x, y) (0 ≤ r ≤ 1), where 0 < x < y are integers, is defined by the following nonlinear recurrence:

a_{0} = x , a_{1} = y ,

and, for n > 1,

a_{n} := ⌊ \frac{a_{n−1}^{2}}{a_{n−2}} + r ⌋ ,

where, as usual, ⌊ x ⌋ denotes the largest integer that is ≤ x. The most important special cases are:

• r = 0, when E_{0}(x, y) is abbreviated T (x, y) ,

• r = \frac{1}{2}, when E_{\frac{1}{2}} (x, y) is written E(x, y) , and

• r = 1, when E_{1}(x, y) is abbreviated S(x, y) . In the present article we will not consider the limiting cases r = 0 or r = 1 (that is, T (x, y) and S(x, y)), although analogous arguments, somewhat more subtle, can be applied to them also. For many choices of initial conditions x, y, Pisot sequences do satisfy linear recurrences that hold for all n (and in this article we present an algorithm–fully implemented in Maple–that rigorously proves it if this is indeed the case), but there are also many examples where there exists a recurrence that is valid for a long time, only to eventually break down. For example, Max Alekseyev [Al] showed that E(5, 17) (sequence A010914) satisfies the linear recurrence

a_{n} = 4a_{n−1} − 2a_{n−2} ,

for all n ≥ 2. On the other hand, David Boyd [B5] found that E(10, 219) (see sequence A007699) satisfies the linear recurrence

a_{n} = 22a_{n−1} − 3a_{n−2} + 18a_{n−3} − 11a_{n−4} ,

for 4 ≤ n ≤ 1402, but that this breaks down at n = 1403. Also, one of us (SBE) found (see the bottom of the output file

http://www.math.rutgers.edu/~zeilberg/tokhniot/oPisot2a.txt) that the Pisot sequence

E(30, 989) (A276396) satisfies the recurrence

a_{n} = 33a_{n−1} − 2a_{n−2} + 30a_{n−3} − 11a_{n−4} ,

for 4 ≤ n ≤ 15888, but that this breaks down at n = 15889. The main tool for explaining why these Pisot sequences sometimes have such doppelgängers (sequences generated by linear recurrences which agree with them for many terms but eventually differ) is the following result:

Theorem (Flor [Fl], Boyd B5]) If E_{r}(x, y) (0 ≤ r ≤ 1) satisfies a linear recurrence then the defining polynomial M(t) of the linear recurrence is either (t − 1)^{2} or else has a single root r_{1} > 1 outside the unit circle with the remaining roots on or inside the unit circle, the roots on the unit circle being simple roots.

As we will see from the analysis and examples below, if there is a second root r_{2} that is just outside the unit circle, the doppelgänger defined by the recurrence can agree with the Pisot sequence for a large number of terms.

How likely is it that a second root r_{2} exists outside the unit circle? If the coefficients of the quotient M(t)/(t − r_{1}) were random (which of course they are not), then studies of the locations of roots of random polynomials suggest that the roots tend to be concentrated in a narrow annulus containing the unit circle (see for example [IZ] and the earlier references cited there). If this were true here then we should expect doppelgängers to be fairly common. Both Cantor [Ca] and Boyd [B1-B5] have carried out systematic studies of various classes of Pisot sequences. It would be nice to have more statistics about the minimal polynomials M(t) that arise.

3. How to Prove that a Proposed Linear Recurrence for a Pisot Sequence Holds for All Values

For the sake of pedagogy, before discussing the general case, in this section we will study a specific example.

The sequence E(4, 7), A010901, let’s call it {a_{n}}, starts with

4, 7, 12, 21, 37, 65, 114, 200, 351, 616, 1081, 1897, 3329, 5842, 10252, 17991, 31572, 55405, 97229, …

The OEIS entry formerly contained the conjecture that this satisfies the linear recurrence

a_{n} = 2a_{n−1} − a_{n−2} + a_{n−3} ,

wth initial conditions

a_{0} = 4 , a_{1} = 7 , a_{2} = 12 ,

together with the remark that this is satisfied for n ≤ 50000. To prove that this holds for all n we proceed as follows (the same method was used by Max Alekseyev [Al] to establish the recurrence for E(5, 17) mentioned above). Recall that by the definition of Pisot sequences

a_{n} := ⌊ \frac{a_{n−1}^{2}}{a_{n−2}} + \frac{1}{2} ⌋ .

Let’s define the sequence b_{n} to be the (obviously unique) sequence satisfying the recurrence

b_{n} = 2b_{n−1} − b_{n−2} + b_{n−3} ,

subject to the initial conditions

b_{0} = 4 , b_{1} = 7 , b_{2} = 12 .

We have to prove that a_{n} = b_{n} for all n ≥ 0. Using the symmetry of the “=” relation, we will prove the equivalent statement that b_{n} = a_{n}. In other words we must show that

b_{n} = ⌊ \frac{b_{n−1}^{2}}{b_{n−2}} + \frac{1}{2} ⌋ .

But, recalling that N = ⌊x⌋ is just shorthand for

N ≤ x < N + 1 ,

our task is to prove that

b_{n} ≤ \frac{b_{n−1}^{2}}{b_{n−2}} + \frac{1}{2} < b_{n} + 1 ,

or equivalently,

−\frac{1}{2} ≤ \frac{b_{n−1}^{2} − b_{n}b_{n−2}}{b_{n−2}} < \frac{1}{2} .

Define the sequence c_{n} by

c_{n} := b_{n−1}^{2} − b_{n}b_{n−2} .

From the linear recurrence defining b_{n}, we know that b_{n} is given explicitly by

b_{n} = 3.902586801 · (1.754877667)^{n}+(0.04870659984 − 0.09364053397 i) (0.1225611669 + 0.7448617670 i)^{n}

+ (0.04870659949 + 0.09364053445 i) (0.1225611669 − 0.7448617670 i)^{n} ,

where we have used floating-point numbers for convenience. (To make this rigorous we could instead use rational interval arithmetic. We emphasize that we do not need to solve the characteristic polynomial of the recurrence exactly, although in this case of course we could, since it is a cubic polynomial.)

It follows that the sequence c_{n} is given by

c_{n} = 0.02472469487 · (0.5698402912)^{n}+(0.4876376523 + 1.233168614 i) (0.2150798545 + 1.307141279 i)^{n}

+ (0.4876376524 − 1.233168615 i) (0.2150798545 − 1.307141279 i)^{n} .

Hence, since the absolute value of the largest terms in c_{n}, 0.2150798545±1.307141279 i, is 1.324717958, we have

|c_{n}| = O(1.324717958^{n}) ,

and similarly

b_{n} = Ω(1.754877667^{n}) ,

where the implied constants can be easily made explicit if desired. It follows that

|\frac{c_{n}}{b_{n−2}} | = O ((\frac{1.324717958}{1.754877667})^{n}) = O((0.7548776664)^{n})

and now one can easily find an N_{0} such that |\frac{c_{n}}{b_{n−2}} | < \frac{1}{2} for n ≥ N_{0}, and the computer can check that this is valid for the first N_{0} values. This completes the proof.

To get the Maple package to carry out this calculation, you would first load the package by typing read `Pisot.txt`; and then running the command

PtoRv(4, 7, 1/2, 12, 60, 50000); .

The arguments to PtoRv are the parameters x, y, r that define the Pisot sequence, then the maximal order of a recurrence you wish to search for (here, 12), then the number of terms of the Pisot sequence E_{r}(x, y) you would like printed (here, 60), and finally the number of terms the program should check before giving up (here, 50000). PtoRv is the verbose version; PtoR is more succinct.

By using this program we were able to prove conjectured recurrences for 21 entries in the OEIS: A010901, A010904, A010906–A010913, A010924, A020698, A020704, A020720, . . ..

4. The General Case

Suppose we have found a putative sequence {b_{n}} that appears to agree with a Pisot sequence. Let b_{n} satisfy a linear recurrence equation of order k with constant coefficients, say

b_{n} = ∑_{i=1}^{k} A_{i}b_{n−i} ,

for some integer coefficients A_{1}, …, A_{k} and given values of b_{0}, …, b_{k−1}.

Let r_{1}, …, r_{k} be the k roots (for the sake of simplicity we assume that they are distinct) of the characteristic polynomial

t^{k} − ∑_{i=1}^{k} A_{i}t^{k−i} = 0 ,

and let r_{1} be the largest root in absolute value, which we assume is real and positive. (This is reasonable, given the theorem in Section 2.) Label the roots so that r_{1} > |r_{2}| ≥ |r_{3}| ≥ … ≥ |r_{k}|.

It follows that b_{n} satisfies a Binet-type formula

b_{n} = ∑_{i=1}^{k} C_{i}r_{i}^{n} ,

for some explicit constants, C_{1}, …, C_{k} that can easily be found by linear algebra, in terms of the initial values b_{0}, …, b_{k−1}. Hence

c_{n} := b_{n−1}^{2} − b_{n}b_{n−2} = (∑_{i=1}^{k} C_{i}r_{i}^{n−1})^{2} − (∑_{i=1}^{k} C_{i}r_{i}^{n}) (∑_{i=1}^{k} C_{i}r_{i}^{n−2})

= ∑_{i=1}^{k} ∑_{j=1}^{k} C_{i}C_{j}(r_{i}^{n−1}r_{j}^{n−1} − r_{i}^{n}r_{j}^{n−2}) = ∑_{i=1}^{k} ∑_{j=1}^{k} C_{i}C_{j}r_{i}^{n−2}r_{j}^{n−2}(r_{i}r_{j} − r_{i}^{2})

= ∑_{{1≤i,j≤k \atop i=j}} C_{i}C_{j}r_{i}^{n−2}r_{j}^{n−2}(r_{i}r_{j} − r_{i}^{2}) + ∑_{{1≤i,j≤k \atop i≠j}} C_{i}C_{j}r_{i}^{n−2}r_{j}^{n−2}(r_{i}r_{j} − r_{i}^{2})

= 0 + ∑_{1≤i<j≤k} C_{i}C_{j}r_{i}^{n−2}r_{j}^{n−2}(2r_{i}r_{j} − r_{i}^{2} − r_{j}^{2})

= − ∑_{1≤i<j≤k} C_{i}C_{j}r_{i}^{n−2}r_{j}^{n−2}(r_{i} − r_{j})^{2} .

Hence |c_{n}| = O((r_{1}|r_{2}|)^{n}). We also have that b_{n} = Ω(r_{1}^{n}). If |r_{2}| < 1, then \frac{c_{n}}{b_{n−2}} goes to zero exponentially fast, and to check that

b_{n} ≤ \frac{b_{n−1}^{2}}{b_{n−2}} + r < b_{n} + 1 ,

once again we need to find an N_{0} such that for n ≥ N_{0}

−r ≤ \frac{c_{n}}{b_{n−2}} < 1 − r ,

and check it for the finitely many cases n < N_{0}.

5. Why does E(30,989)’s Doppelgänger Hold for so Many Terms? We have already mentioned that the Pisot sequence E(30, 989) satisfies the recurrence

a_{n} = 33a_{n−1} − 2a_{n−2} + 30a_{n−3} − 11a_{n−4} ,

for 4 ≤ n ≤ 15888 but fails for n = 15889. If we apply the above analysis to this recurrence, then we find that r_{2} is just outside the unit circle: |r_{2}| = 1.00003759711047, and so b_{n} = a_{n} as long as

0.2751394860 · (1.00003759711047)^{n} < \frac{1}{2} .

Taking logarithms

(0.00003759629325) · n < 0.5973299074 ,

this is true for n ≤ 15888 but fails beyond that point.

6. Infinite Families There are many infinite families of Pisot sequences that do satisfy linear recurrences. Already in 1938 Pisot [Pi] showed that if x = 2 or x = 3 then E(x, y) satisfies a linear recurrence of low order, and determined the coefficients. A very large number of other families with x in the range 4 to 20 can be viewed here:

http://www.math.rutgers.edu/~zeilberg/tokhniot/oPisot5.txt .

For the record here are the first few examples with x = 4, 5, 6. We denote the unique solution of the linear recurrence (of order m)

a_{n} = ∑_{i=1}^{m} A_{i}a_{n−i} , a_{0} = d_{1}, …, a_{m−1} = d_{m} ,

by the pair of lists

[[d_{1}, …, d_{m}] , [A_{1}, …, A_{m}]] .

For k ≥ 1 (and sometimes, if it makes sense, for k = 0), we have:

E (4, 16 k + 1) = [[4, 16 k + 1], [4 k, k]] ,
E (4, 16 k + 2) = [[4, 16 k + 2, 64 k^{2} + 16 k + 1], [1 + 4 k, −2 k, −k]] ,
E (4, 16 k + 5) = [[4, 16 k + 5], [2 + 4 k, −1 − 3 k]] ,
E (4, 16 k + 7) = [[4, 16 k + 7, 64 k^{2} + 56 k + 12], [2 + 4 k, −1 − k, 1 + 2 k]] ,
E (4, 16 k + 9) = [[4, 16 k + 9, 64 k^{2} + 72 k + 20], [2 + 4 k, k, 1 + 2 k]] ,
E (4, 16 k + 10) = [[4, 16 k + 10, 64 k^{2} + 80 k + 25], [3 + 4 k, −2 − 2 k, 2 + 3 k]] ,
E (4, 16 k + 11) = [[4, 16 k + 11], [2 + 4 k, 2 + 3 k]] ,
E (4, 16 k + 14) = [[4, 16 k + 14, 64 k^{2} + 112 k + 49], [4 + 4 k, −2 − 2 k, 1 + k]] ,
E (4, 16 k + 15) = [[4, 16 k + 15], [4 + 4 k, −1 − k]] ,
. . . . . . . . .
E (5, 25 k + 1) = [[5, 25 k + 1], [5 k, k]] ,
E (5, 25 k + 2) = [[5, 25 k + 2, 125 k^{2} + 20 k + 1], [5 k, 2 k, k]] ,

E (5, 25 k + 3) = [[5, 25 k + 3, 125 k^{2} + 30 k + 2, 625 k^{3} + 225 k^{2} + 29 k + 1], [5 k, 3 k, 2 k, k]] .

. . . . . . . . .
E (6, 36 k + 1) = [[6, 36 k + 1], [6 k, k]] ,
E (6, 36 k + 2) = [[6, 36 k + 2, 216 k^{2} + 24 k + 1], [6 k, 2 k, k]] ,

E (6, 36 k + 3) = [[6, 36 k + 3, 216 k^{2} + 36 k + 2, 1296 k^{3} + 324 k^{2} + 33 k + 1], [1 + 6 k, −3 k, −k, −k]] .

. . . . . . . . .

Note that Pisot [P1], Cantor [C2], Boyd [B5] already observed that the Pisot sequences E_{r}(x, y) tend to form families whose properties depend on the value of y mod x^{2}, That is, the sequences E_{r}(x, kx^{2} + j), k = 0, 1, 2, … all tend to satisfy similar linear recurrences, or appear not to satisfy such a recurrence. The above examples are consistent with this observation.

It is likely that some of our results for x = 4 and 5 were already known to Galyean [Ga], but we have not been able to get access to his dissertation.

It is also possible to find doubly-infinite (i.e. two-parameter) families, but we stop here.

7. Higher-Order Generalizations

A crucial property of Pisot sequences is that a_{n}a_{n+2} − a_{n+1}^{2} is small compared to a_{n}. Since

a_{n}a_{n+2} − a_{n+1}^{2} = det ( \begin{matrix}a_{n} & a_{n+1} \\ a_{n+1} & a_{n+2} \end{matrix} ) ,

it is natural to generalize the definition, and to consider sequences for which, for some s > 1, the Hankel determinant

Δ_{s} := det ( \begin{matrix}a_{n} & … & a_{n+s} \\ a_{n+1} & … & a_{n+s+1} \\ … & … & … \\ … \\ … & … & … \\ a_{n+s} & … & a_{n+2s} \end{matrix} )

is small.

Note that for any sequence that satisfies a linear recurrence with constant coefficients of order s, the above determinant is identically zero.

Let us define F_{s} and G_{s} by writing

Δ_{s} = a_{n+2s}F_{s}(a_{1}, …, a_{n+2s−1}) − G_{s}(a_{1}, …, a_{n+2s−1}) .

Then we define an order-s Pisot sequence, E_{r}(a_{0}, …, a_{2s−1}) with parameter r (0 ≤ r ≤ 1) by the rules that for 0 ≤ n ≤ 2s − 1 the value is a_{n}, and for n ≥ 0 we have

a_{n+2s} = ⌊ \frac{G_{s}(a_{1}, …, a_{n+2s−1})}{F_{s}(a_{1}, …, a_{n+2s−1})} + r ⌋ .

A calculation analogous to that in Section 4 shows that a necessary condition for a linear recurrence with constant coefficients to be an order-s generalized Pisot sequence is that the (s + 1)-st largest absolute value of the roots is less then 1. (Presumably there is also an analog of the theorem in Section 2 which applies here.) See the output file

http://www.math.rutgers.edu/ zeilberg/tokhniot/oPisot4.txt ,

for numerous examples.

8. References

[Al] Max Alekseyev, Comments on Sequence A010914, Sep. 3 2013; https://oeis.org/A010914.

[Ba] Charles Babbage, Of induction, from Essays in the Philosophy of Analysis, circa 1820, typeset and edited by Martin Fagereng Johansen, 2013; available from

http://martinfjohansen.com/ofinduction/ofinduction-2013-11-11-firstdraft.pdf .

[B1] David W. Boyd, Pisot sequences which satisfy no linear recurrences, Acta Arith., 32 (1977) 89–98.

[B2] David W. Boyd, Some integer sequences related to the Pisot sequences, Acta Arith., 34 (1979), 295–305.

[B3] David W. Boyd, On linear recurrence relations satisfied by Pisot sequences, Acta Arith., 47 (1986) 13–27; 54 (1990), 255–256.

[B4] David W. Boyd, Pisot sequences which satisfy no linear recurrences, II, Acta Arith. 48 (1987) 191–195.

[B5] David W. Boyd, Linear recurrence relations for some generalized Pisot sequences, in Advances in Number Theory (Kingston ON, 1991), pp. 333–340, Oxford Univ. Press, New York, 1993; with updates from 1996 and 1999; available from https://www.researchgate.net/profile/David Boyd7/publication/262181133 Linear recurrence relations for some generalized Pisot sequences - annotated with corrections and additions/links/00b7d536d49781037f000000.pdf .

[C1] David G. Cantor, Investigation of T-numbers and E-sequences, in A. O. L. Atkins and B. J. Birch, eds., Computers in Number Theory, Acad. Press, NY, 1971, pp. 137–140.

[C2] David G. Cantor, On families of Pisot E-sequences, Ann. Scient. Éc. Norm. Sup., 9 (1976), 283–308.

[E] Leonhard Euler, Exemplum memorabile inductionis fallacis, Opera Omnia, Series Prima, 15 (1911), 50–69, Teubner. Leipzig, Germany.

[Fl] Peter Flor, Über eine Klasse von Folgen natürlicher Zahlen, Math. Annalen, 140 (1960), 299–307.

[Ga] Paul H. Galyean, On Linear Recurrence Relations for E-Sequences, Ph.D. Dissertation, Univ. California Los Angeles, 1971 (unpublished).

[G1] Richard K. Guy, The strong law of small numbers, Amer. Math. Monthly, 95 (1988), 697–712.

[G2] Richard K. Guy, The second strong law of small numbers, Math. Mag. 63 (1990), 3–20.

[IZ] Ildar Ibragimov and Dmitry Zaporozhets, On distribution of zeros of random polynomials in complex plane, in Prokhorov and Contemporary Probability Theory, Springer, 2013, pp. 303–323; available from arXiv:1102.3517..

[OEIS] The OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, https://oeis.org.

[Pi] Charles Pisot, La répartition modulo 1 et les nombres algébriques, Ann. Scuola Norm. Sup. Pisa Cl. Sci., 7 (1938), 205–248.

Shalosh B. Ekhad, c/o D. Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

N. J. A. Sloane, The OEIS Foundation Inc, 11 South Adelaide Ave, Highland Park, NJ 08904, USA, and Department of Mathematics, Rutgers University (New Brunswick); njasloane at gmail dot com ; http://neilsloane.com/ .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA;

DoronZeil at gmail dot com ; http://www.math.rutgers.edu/~zeilberg/ .

Exclusively published in The Personal Journal of Shalosh B. Ekhad and Doron Zeilberger

(http://www.math.rutgers.edu/~zeilberg/pj.html), N. J. A. Sloane’s Home Page
(http://neilsloane.com/), and the arxiv.org .

Sept. 20, 2016