pisot module

This module is a translation of (part of) Doron Zeilberger’s Pisot.txt from Maple to Python.

Pisot.txt is a Maple program that implements procedures to assist in the study of Pisot sequences. In particular, it can guess (and prove!) whether or not a given Pisot sequence satisfies a linear recurrence relation with constant coefficients (up to all degrees checked). To do this, it relies on the Maple program Cfinite.txt, also written by Zeilberger.

Due to its mathematical complexity, Pisot.txt can be difficult to read. This is exacerbated by the fact that Maple, though useful in its domain, is not an elegant programming language. I hope that this Python implementation will (eventually) provide a more accessible demonstration of the applications of symbollic computing.

class pisot.Pisot(x, y, r)

Bases: sympy.series.sequences.SeqBase

This class defines basic methods for dealing with Pisot sequences.

The Pisot sequence \(E_r(x, y)\) is defined by

\[\begin{split}\begin{align} a_0 &= x \\ a_1 &= y \\ a_n &= \left\lfloor \frac{a_{n - 1}^2}{a_{n - 2}} + r \right\rfloor, \end{align}\end{split}\]

where \(0 < x < y\) are integers, and \(r\) is some constant.

default_assumptions = {'commutative': True}

find_cfinite_recurrence(n_terms)

Try to guess a C-finite recurrence of the given degree that the first n_terms terms might satisfy, using sympy’s find_linear_recurrence() function.

N_terms:Number of terms to check. Returns:A CFinite instance or None.

gen()

Yield a generator of terms.

get_terms(k)

Compute the first k terms as a list.

interval

Interval on which sequence is defined ((0, \(\infty\))).

is_commutative = True

start

Start of sequence (0).

stop

End of sequence (\(\infty\)).

pisot.pisot_root(c_seq)

Compute the absolute value of the second-largest root of the characteristic equation for the C-finite sequence, excluding any possible “1”s. It is assumed that the single root case is handled before calling this.

Zeilberger does additional things in this method. If there are repeated roots, we return None.

Parameters:c_seq – CFinite instance. Returns:Floating point evaluation of the absolute value of the root, or None.

pisot.pisot_to_cfinite(pisot, guess_length, check_length, verbose=False)

Check if the given Pisot sequence satisfies a linear recurrence relation with finite coefficients.

We “correct” (I have not yet tried the single root case) the behavior of Pisot.txt as follows:

Let p be the single coefficient. Then, the conjectured form is \(a_n = p a_{n - 1}\), or \(a_n = p^n x\). Rewritten, the conjecture is that \(a_n = b_n\), where \(b_n = p^n x\) for some real p. This is true iff

\[p^n x = floor(p^n x + r),\]

which holds iff 0 <= r < 1.

That is, if it looks like the sequence is a trivial geometric sequence, then it is as long as 0 <= r < 1.

More formally: If \(y / x = p\), \(p^n x\) is an integer for all nonnegative integers n, and 0 <= r < 1, then \(E_r(x, y)\) is given by \(a_n = p^n x\).

As an important special case, if \(x\) divides \(y\) and 0 <= r < 1, then this is true. We only handle this case.

Pisot:Pisot sequence. Guess_length:Number of terms to use when guessing the recurrence. This should be somewhat small. If the sequence fails to satisfy a linear recurrence at a large number, then this method will spend a long time trying to look for one. Check_length:Number of terms of the sequence to check the conjectured linear recurrence for. This should be a large number. Returns:A CFinite instance, or None.