Infinite sequences

[Travis Scrimshaw]

Hey everyone,

   While I was looking at http://trac.sagemath.org/sage_trac/ticket/13556, I noticed what I believe to be a greater underlying problem with sage in that infinite sequences are not handled (gracefully). In particular, sage tries to construct infinite sequences/lists/tuples when given an infinite iterable set `L` (ex. `QQ` or `(1..)` or `Partitions()`)

{{{

sage: list(L)

sage: tuple(L)

sage: Sequence(L)

}}}

I doubt we could do anything about `list` or `tuple` since they are python built-ins, but what about `Sequence`? My first thought is to raise a `ValueError` if we give it an infinite list, and I think we need a method for the ellipsis iterator which checks if it is finite.

   I also noted that `FreeModule` does not support infinite dimensions by (naively) calling `FreeModule(QQ, oo)`. However I believe we can still work in infinite dimensions by working in `CombinatorialFreeModule(QQ, ZZ)`. In either case, this may only be suitable if we consider it as a direct sum (and implementing using the sparse free modules)...

Thoughts?

Best,

Travis

[John H Palmieri]

On Friday, November 16, 2012 12:55:00 PM UTC-8, Travis Scrimshaw wrote:

   I also noted that `FreeModule` does not support infinite dimensions by (naively) calling `FreeModule(QQ, oo)`. However I believe we can still work in infinite dimensions by working in `CombinatorialFreeModule(QQ, ZZ)`. In either case, this may only be suitable if we consider it as a direct sum (and implementing using the sparse free modules)...

CombinatorialFreeModule(QQ, basis) works fine if 'basis' is infinite:

sage: CombinatorialFreeModule(QQ, ZZ)
Free module generated by Integer Ring over Rational Field
sage: CombinatorialFreeModule(QQ, Partitions())
Free module generated by Partitions over Rational Field

Just don't ask for a list of the basis elements ;)

--
John

[Sébastien Labbé]

Hi,

In combinatorics on words, we often deal with infinite sequences, and there is code in Sage to deal with these things. After that, I don't know if the question you want to ask to those objects are the same as the problems considered in combinatorics on words (like, computing the factor complexity, amongst other things). But, at least, you can take a look at it to see how it works.

So, an infinite word can be defined as a function from the non negative integers to an certain alphabet :

sage: Word(lambda n: n^3 % 7)
word: 0116166011616601161660116166011616601161...

Or as an infinite iterator :

sage: Word(primes(0, infinity))
word: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,...

Well known infinite sequence on {0,1} include the Fibonacci sequence :

sage: words.FibonacciWord()
word: 0100101001001010010100100101001001010010...

The Fibonacci word is also the infinite fixed point of the following morphism (another way of creating an infinite sequence in Sage) :

sage: m = WordMorphism('0->01,1->0')
sage: m.fixed_point('0')
word: 0100101001001010010100100101001001010010...

For any infinite word, there are some methods available, like get the i^th term or slice it :

sage: P = Word(primes(0, infinity))
sage: P[1000]
7927
sage: P[100000:100006]
word: 1299721,1299743,1299763,1299791,1299811,1299817

In this last case, it returns a finite word :

sage: type(_)
<class 'sage.combinat.words.word.FiniteWord_iter_with_caching'>

Compute the finite differences, and so on...

sage: P.finite_differences()
word: 1,2,2,4,2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,4,6,2,10,2,6,6,4,6,6,...

Cheers,

Sébastien