Streams

This module provides lazy implementations of basic operators on streams. The classes implemented in this module can be used to build up more complex streams for different kinds of series (Laurent, Dirichlet, etc.).

EXAMPLES:

Streams can be used as data structure for lazy Laurent series:

sage: L.<z> = LazyLaurentSeriesRing(ZZ)
sage: f = L(lambda n: n, valuation=0)
sage: f
z + 2*z^2 + 3*z^3 + 4*z^4 + 5*z^5 + 6*z^6 + O(z^7)
sage: type(f._coeff_stream)
<class 'sage.data_structures.stream.Stream_function'>

There are basic unary and binary operators available for streams. For example, we can add two streams:

sage: from sage.data_structures.stream import *
sage: f = Stream_function(lambda n: n, True, 0)
sage: [f[i] for i in range(10)]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sage: g = Stream_function(lambda n: 1, True, 0)
sage: [g[i] for i in range(10)]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
sage: h = Stream_add(f, g, True)
sage: [h[i] for i in range(10)]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

We can subtract one stream from another:

sage: h = Stream_sub(f, g, True)
sage: [h[i] for i in range(10)]
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8]

There is a Cauchy product on streams:

sage: h = Stream_cauchy_mul(f, g, True)
sage: [h[i] for i in range(10)]
[0, 1, 3, 6, 10, 15, 21, 28, 36, 45]

We can compute the inverse corresponding to the Cauchy product:

sage: ginv = Stream_cauchy_invert(g)
sage: h = Stream_cauchy_mul(f, ginv, True)
sage: [h[i] for i in range(10)]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Two streams can be composed:

sage: g = Stream_function(lambda n: n, True, 1)
sage: h = Stream_cauchy_compose(f, g, True)
sage: [h[i] for i in range(10)]
[0, 1, 4, 14, 46, 145, 444, 1331, 3926, 11434]

There is a unary negation operator:

sage: h = Stream_neg(f, True)
sage: [h[i] for i in range(10)]
[0, -1, -2, -3, -4, -5, -6, -7, -8, -9]

More generally, we can multiply by a scalar:

sage: h = Stream_lmul(f, 2, True)
sage: [h[i] for i in range(10)]
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

Finally, we can apply an arbitrary functions to the elements of a stream:

sage: h = Stream_map_coefficients(f, lambda n: n^2, True)
sage: [h[i] for i in range(10)]
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

AUTHORS:

• Kwankyu Lee (2019-02-24): initial version

• Tejasvi Chebrolu, Martin Rubey, Travis Scrimshaw (2021-08): refactored and expanded functionality

class sage.data_structures.stream.Stream(true_order)

Bases: object

Abstract base class for all streams.

INPUT:

• true_order – boolean; if the approximate order is the actual order

Note

An implementation of a stream class depending on other stream classes must not access coefficients or the approximate order of these, in order not to interfere with lazy definitions for Stream_uninitialized.

If an approximate order or even the true order is known, it must be set after calling super().__init__.

Otherwise, a lazy attribute _approximate_order has to be defined. Any initialization code depending on the approximate orders of input streams can be put into this definition.

However, keep in mind that (trivially) this initialization code is not executed if _approximate_order is set to a value before it is accessed.

is_nonzero()

Return True if and only if this stream is known to be non-zero.

The default implementation is False.

EXAMPLES:

sage: from sage.data_structures.stream import Stream
sage: CS = Stream(1)
sage: CS.is_nonzero()
False

is_uninitialized()

Return True if self is an uninitialized stream.

The default implementation is False.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_zero
sage: zero = Stream_zero()
sage: zero.is_uninitialized()
False

class sage.data_structures.stream.Stream_add(left, right, is_sparse)

Bases: Stream_binaryCommutative

Operator for addition of two coefficient streams.

INPUT:

• left – Stream of coefficients on the left side of the operator

• right – Stream of coefficients on the right side of the operator

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_add, Stream_function)
sage: f = Stream_function(lambda n: n, True, 0)
sage: g = Stream_function(lambda n: 1, True, 0)
sage: h = Stream_add(f, g, True)
sage: [h[i] for i in range(10)]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
sage: u = Stream_add(g, f, True)
sage: [u[i] for i in range(10)]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

get_coefficient(n)

Return the n-th coefficient of self.

INPUT:

• n – integer; the degree for the coefficient

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_function, Stream_add)
sage: f = Stream_function(lambda n: n, True, 0)
sage: g = Stream_function(lambda n: n^2, True, 0)
sage: h = Stream_add(f, g, True)
sage: h.get_coefficient(5)
30
sage: [h.get_coefficient(i) for i in range(10)]
[0, 2, 6, 12, 20, 30, 42, 56, 72, 90]

class sage.data_structures.stream.Stream_binary(left, right, is_sparse)

Bases: Stream_inexact

Base class for binary operators on coefficient streams.

INPUT:

• left – Stream for the left side of the operator

• right – Stream for the right side of the operator

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_function, Stream_add, Stream_sub)
sage: f = Stream_function(lambda n: 2*n, True, 0)
sage: g = Stream_function(lambda n: n, True, 1)
sage: h = Stream_add(f, g, True)
sage: [h[i] for i in range(10)]
[0, 3, 6, 9, 12, 15, 18, 21, 24, 27]
sage: h = Stream_sub(f, g, True)
sage: [h[i] for i in range(10)]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

is_uninitialized()

Return True if self is an uninitialized stream.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_uninitialized, Stream_sub, Stream_function
sage: C = Stream_uninitialized(0)
sage: F = Stream_function(lambda n: n, True, 0)
sage: B = Stream_sub(F, C, True)
sage: B.is_uninitialized()
True
sage: Bp = Stream_sub(F, F, True)
sage: Bp.is_uninitialized()
False

class sage.data_structures.stream.Stream_binaryCommutative(left, right, is_sparse)

Bases: Stream_binary

Base class for commutative binary operators on coefficient streams.

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_function, Stream_add)
sage: f = Stream_function(lambda n: 2*n, True, 0)
sage: g = Stream_function(lambda n: n, True, 1)
sage: h = Stream_add(f, g, True)
sage: [h[i] for i in range(10)]
[0, 3, 6, 9, 12, 15, 18, 21, 24, 27]
sage: u = Stream_add(g, f, True)
sage: [u[i] for i in range(10)]
[0, 3, 6, 9, 12, 15, 18, 21, 24, 27]
sage: h == u
True

class sage.data_structures.stream.Stream_cauchy_compose(f, g, is_sparse)

Bases: Stream_binary

Return f composed by g.

This is the composition \((f \circ g)(z) = f(g(z))\).

INPUT:

• f – a Stream

• g – a Stream with positive order

EXAMPLES:

sage: from sage.data_structures.stream import Stream_cauchy_compose, Stream_function
sage: f = Stream_function(lambda n: n, True, 1)
sage: g = Stream_function(lambda n: 1, True, 1)
sage: h = Stream_cauchy_compose(f, g, True)
sage: [h[i] for i in range(10)]
[0, 1, 3, 8, 20, 48, 112, 256, 576, 1280]
sage: u = Stream_cauchy_compose(g, f, True)
sage: [u[i] for i in range(10)]
[0, 1, 3, 8, 21, 55, 144, 377, 987, 2584]

get_coefficient(n)

Return the n-th coefficient of self.

INPUT:

• n – integer; the degree for the coefficient

EXAMPLES:

sage: from sage.data_structures.stream import Stream_function, Stream_cauchy_compose
sage: f = Stream_function(lambda n: n, True, 1)
sage: g = Stream_function(lambda n: n^2, True, 1)
sage: h = Stream_cauchy_compose(f, g, True)
sage: h[5] # indirect doctest
527
sage: [h[i] for i in range(10)] # indirect doctest
[0, 1, 6, 28, 124, 527, 2172, 8755, 34704, 135772]

class sage.data_structures.stream.Stream_cauchy_invert(series, approximate_order=None)

Bases: Stream_unary

Operator for multiplicative inverse of the stream.

INPUT:

• series – a Stream

• approximate_order – None, or a lower bound on the order of the resulting stream

Instances of this class are always dense, because of mathematical necessities.

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_cauchy_invert, Stream_function)
sage: f = Stream_function(lambda n: 1, True, 1)
sage: g = Stream_cauchy_invert(f)
sage: [g[i] for i in range(10)]
[-1, 0, 0, 0, 0, 0, 0, 0, 0, 0]

is_nonzero()

Return True if and only if this stream is known to be non-zero.

An assumption of this class is that it is non-zero.

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_cauchy_invert, Stream_function)
sage: f = Stream_function(lambda n: n^2, False, 1)
sage: g = Stream_cauchy_invert(f)
sage: g.is_nonzero()
True

iterate_coefficients()

A generator for the coefficients of self.

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_cauchy_invert, Stream_function)
sage: f = Stream_function(lambda n: n^2, False, 1)
sage: g = Stream_cauchy_invert(f)
sage: n = g.iterate_coefficients()
sage: [next(n) for i in range(10)]
[1, -4, 7, -8, 8, -8, 8, -8, 8, -8]

class sage.data_structures.stream.Stream_cauchy_mul(left, right, is_sparse)

Bases: Stream_binary

Operator for multiplication of two coefficient streams using the Cauchy product.

We are not assuming commutativity of the coefficient ring here, only that the coefficient ring commutes with the (implicit) variable.

INPUT:

• left – Stream of coefficients on the left side of the operator

• right – Stream of coefficients on the right side of the operator

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_cauchy_mul, Stream_function)
sage: f = Stream_function(lambda n: n, True, 0)
sage: g = Stream_function(lambda n: 1, True, 0)
sage: h = Stream_cauchy_mul(f, g, True)
sage: [h[i] for i in range(10)]
[0, 1, 3, 6, 10, 15, 21, 28, 36, 45]
sage: u = Stream_cauchy_mul(g, f, True)
sage: [u[i] for i in range(10)]
[0, 1, 3, 6, 10, 15, 21, 28, 36, 45]

get_coefficient(n)

Return the n-th coefficient of self.

INPUT:

• n – integer; the degree for the coefficient

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_function, Stream_cauchy_mul)
sage: f = Stream_function(lambda n: n, True, 0)
sage: g = Stream_function(lambda n: n^2, True, 0)
sage: h = Stream_cauchy_mul(f, g, True)
sage: h.get_coefficient(5)
50
sage: [h.get_coefficient(i) for i in range(10)]
[0, 0, 1, 6, 20, 50, 105, 196, 336, 540]

is_nonzero()

Return True if and only if this stream is known to be non-zero.

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_function,
....:     Stream_cauchy_mul, Stream_cauchy_invert)
sage: f = Stream_function(lambda n: n, True, 1)
sage: g = Stream_cauchy_mul(f, f, True)
sage: g.is_nonzero()
False
sage: fi = Stream_cauchy_invert(f)
sage: h = Stream_cauchy_mul(fi, fi, True)
sage: h.is_nonzero()
True

class sage.data_structures.stream.Stream_cauchy_mul_commutative(left, right, is_sparse)

Bases: Stream_cauchy_mul, Stream_binaryCommutative

Operator for multiplication of two coefficient streams using the Cauchy product for commutative multiplication of coefficients.

class sage.data_structures.stream.Stream_derivative(series, shift, is_sparse)

Bases: Stream_unary

Operator for taking derivatives of a non-exact stream.

INPUT:

• series – a Stream

• shift – a positive integer

• is_sparse – boolean

is_nonzero()

Return True if and only if this stream is known to be non-zero.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_exact, Stream_derivative
sage: f = Stream_exact([1,2])
sage: Stream_derivative(f, 1, True).is_nonzero()
True
sage: Stream_derivative(f, 2, True).is_nonzero() # it might be nice if this gave False
True

class sage.data_structures.stream.Stream_dirichlet_convolve(left, right, is_sparse)

Bases: Stream_binary

Operator for the Dirichlet convolution of two streams.

INPUT:

• left – Stream of coefficients on the left side of the operator

• right – Stream of coefficients on the right side of the operator

The coefficient of \(n^{-s}\) in the convolution of \(l\) and \(r\) equals \(\sum_{k | n} l_k r_{n/k}\).

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_dirichlet_convolve, Stream_function, Stream_exact)
sage: f = Stream_function(lambda n: n, True, 1)
sage: g = Stream_exact([0], constant=1)
sage: h = Stream_dirichlet_convolve(f, g, True)
sage: [h[i] for i in range(1, 10)]
[1, 3, 4, 7, 6, 12, 8, 15, 13]
sage: [sigma(n) for n in range(1, 10)]
[1, 3, 4, 7, 6, 12, 8, 15, 13]

sage: u = Stream_dirichlet_convolve(g, f, True)
sage: [u[i] for i in range(1, 10)]
[1, 3, 4, 7, 6, 12, 8, 15, 13]

get_coefficient(n)

Return the n-th coefficient of self.

INPUT:

• n – integer; the degree for the coefficient

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_dirichlet_convolve, Stream_function, Stream_exact)
sage: f = Stream_function(lambda n: n, True, 1)
sage: g = Stream_exact([0], constant=1)
sage: h = Stream_dirichlet_convolve(f, g, True)
sage: h.get_coefficient(7)
8
sage: [h[i] for i in range(1, 10)]
[1, 3, 4, 7, 6, 12, 8, 15, 13]

class sage.data_structures.stream.Stream_dirichlet_invert(series, is_sparse)

Bases: Stream_unary

Operator for inverse with respect to Dirichlet convolution of the stream.

INPUT:

• series – a Stream

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_dirichlet_invert, Stream_function)
sage: f = Stream_function(lambda n: 1, True, 1)
sage: g = Stream_dirichlet_invert(f, True)
sage: [g[i] for i in range(10)]
[0, 1, -1, -1, 0, -1, 1, -1, 0, 0]
sage: [moebius(i) for i in range(10)]                                           # needs sage.libs.pari
[0, 1, -1, -1, 0, -1, 1, -1, 0, 0]

get_coefficient(n)

Return the n-th coefficient of self.

INPUT:

• n – integer; the degree for the coefficient

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_exact, Stream_dirichlet_invert)
sage: f = Stream_exact([0, 3], constant=2)
sage: g = Stream_dirichlet_invert(f, True)
sage: g.get_coefficient(6)
2/27
sage: [g[i] for i in range(8)]
[0, 1/3, -2/9, -2/9, -2/27, -2/9, 2/27, -2/9]

class sage.data_structures.stream.Stream_exact(initial_coefficients, constant=None, degree=None, order=None)

Bases: Stream

A stream of eventually constant coefficients.

INPUT:

• initial_values – a list of initial values

• is_sparse – boolean; specifies whether the stream is sparse

• order – integer (default: 0); determining the degree of the first element of initial_values

• degree – integer (optional); determining the degree of the first element which is known to be equal to constant

• constant – integer (default: 0); the coefficient of every index larger than or equal to degree

Warning

The convention for order is different to the one in sage.rings.lazy_series_ring.LazySeriesRing, where the input is shifted to have the prescribed order.

is_nonzero()

Return True if and only if this stream is known to be non-zero.

An assumption of this class is that it is non-zero.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_exact
sage: s = Stream_exact([2], order=-1, degree=2, constant=1)
sage: s.is_nonzero()
True

order()

Return the order of self, which is the minimum index n such that self[n] is non-zero.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_exact
sage: s = Stream_exact([1])
sage: s.order()
0

class sage.data_structures.stream.Stream_function(function, is_sparse, approximate_order, true_order=False)

Bases: Stream_inexact

Class that creates a stream from a function on the integers.

INPUT:

• function – a function that generates the coefficients of the stream

• is_sparse – boolean; specifies whether the stream is sparse

• approximate_order – integer; a lower bound for the order of the stream

Note

We assume for equality that function is a function in the mathematical sense.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_function
sage: f = Stream_function(lambda n: n^2, False, 1)
sage: f[3]
9
sage: [f[i] for i in range(10)]
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

sage: f = Stream_function(lambda n: 1, False, 0)
sage: n = f.iterate_coefficients()
sage: [next(n) for _ in range(10)]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

sage: f = Stream_function(lambda n: n, True, 0)
sage: f[4]
4

class sage.data_structures.stream.Stream_inexact(is_sparse, true_order)

Bases: Stream

An abstract base class for the stream when we do not know it is eventually constant.

In particular, a cache is provided.

INPUT:

• is_sparse – boolean; whether the implementation of the stream is sparse

• true_order – boolean; if the approximate order is the actual order

If the cache is dense, it begins with the first non-zero term.

is_nonzero()

Return True if and only if the cache contains a non-zero element.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_function
sage: CS = Stream_function(lambda n: 1/n, False, 1)
sage: CS.is_nonzero()
False
sage: CS[1]
1
sage: CS.is_nonzero()
True

iterate_coefficients()

A generator for the coefficients of self.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_function, Stream_cauchy_compose
sage: f = Stream_function(lambda n: 1, False, 1)
sage: g = Stream_function(lambda n: n^3, False, 1)
sage: h = Stream_cauchy_compose(f, g, True)
sage: n = h.iterate_coefficients()
sage: [next(n) for i in range(10)]
[1, 9, 44, 207, 991, 4752, 22769, 109089, 522676, 2504295]

order()

Return the order of self, which is the minimum index n such that self[n] is non-zero.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_function
sage: f = Stream_function(lambda n: n, True, 0)
sage: f.order()
1

class sage.data_structures.stream.Stream_infinite_operator(iterator)

Bases: Stream

Stream defined by applying an operator an infinite number of times.

The iterator returns elements \(s_i\) to compute an infinite operator. The valuation of \(s_i\) is weakly increasing as we iterate over \(I\) and there are only finitely many terms with any fixed valuation. In particular, this assumes the result is nonzero.

Warning

This does not check that the input is valid.

INPUT:

• iterator – the iterator for the factors

is_nonzero()

Return True if and only if this stream is known to be nonzero.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_infinite_sum
sage: L.<t> = LazyLaurentSeriesRing(QQ)
sage: it = (t^n / (1 - t) for n in PositiveIntegers())
sage: f = Stream_infinite_sum(it)
sage: f.is_nonzero()
True

order()

Return the order of self, which is the minimum index n such that self[n] is nonzero.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_infinite_sum
sage: L.<t> = LazyLaurentSeriesRing(QQ)
sage: it = (t^(5+n) / (1 - t) for n in PositiveIntegers())
sage: f = Stream_infinite_sum(it)
sage: f.order()
6

class sage.data_structures.stream.Stream_infinite_product(iterator)

Bases: Stream_infinite_operator

Stream defined by an infinite product.

The iterator returns elements \(p_i\) to compute the product \(\prod_{i \in I} (1 + p_i)\). See Stream_infinite_operator for restrictions on the \(p_i\).

INPUT:

• iterator – the iterator for the factors

apply_operator(next_obj)

Apply the operator to next_obj.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_infinite_product
sage: L.<t> = LazyLaurentSeriesRing(QQ)
sage: it = (t^n / (1 - t) for n in PositiveIntegers())
sage: f = Stream_infinite_product(it)
sage: f._advance()
sage: f._advance()  # indirect doctest
sage: f._cur
1 + t + 2*t^2 + 4*t^3 + 6*t^4 + 9*t^5 + 13*t^6 + O(t^7)

initial(obj)

Set the initial data.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_infinite_product
sage: L.<t> = LazyLaurentSeriesRing(QQ)
sage: it = (t^n / (1 - t) for n in PositiveIntegers())
sage: f = Stream_infinite_product(it)
sage: f._cur is None
True
sage: f._advance()  # indirect doctest
sage: f._cur
1 + t + 2*t^2 + 3*t^3 + 4*t^4 + 5*t^5 + 6*t^6 + O(t^7)

class sage.data_structures.stream.Stream_infinite_sum(iterator)

Bases: Stream_infinite_operator

Stream defined by an infinite sum.

The iterator returns elements \(s_i\) to compute the product \(\sum_{i \in I} s_i\). See Stream_infinite_operator for restrictions on the \(s_i\).

INPUT:

• iterator – the iterator for the factors

apply_operator(next_obj)

Apply the operator to next_obj.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_infinite_sum
sage: L.<t> = LazyLaurentSeriesRing(QQ)
sage: it = (t^(n//2) / (1 - t) for n in PositiveIntegers())
sage: f = Stream_infinite_sum(it)
sage: f._advance()
sage: f._advance()  # indirect doctest
sage: f._cur
1 + 3*t + 4*t^2 + 4*t^3 + 4*t^4 + O(t^5)

initial(obj)

Set the initial data.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_infinite_sum
sage: L.<t> = LazyLaurentSeriesRing(QQ)
sage: it = (t^n / (1 - t) for n in PositiveIntegers())
sage: f = Stream_infinite_sum(it)
sage: f._cur is None
True
sage: f._advance()  # indirect doctest
sage: f._cur
t + 2*t^2 + 2*t^3 + 2*t^4 + O(t^5)

class sage.data_structures.stream.Stream_integral(series, integration_constants, is_sparse)

Bases: Stream_unary

Operator for taking integrals of a non-exact stream.

INPUT:

• series – a Stream

• integration_constants – a list of integration constants

• is_sparse – boolean

get_coefficient(n)

Return the n-th coefficient of self.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_function, Stream_integral
sage: f = Stream_function(lambda n: n + 1, True, -3)
sage: [f[i] for i in range(-3, 4)]
[-2, -1, 0, 1, 2, 3, 4]
sage: f2 = Stream_integral(f, [0], True)
sage: [f2.get_coefficient(i) for i in range(-3, 5)]
[0, 1, 1, 0, 1, 1, 1, 1]

sage: f = Stream_function(lambda n: (n + 1)*(n+2), True, 2)
sage: [f[i] for i in range(-1, 4)]
[0, 0, 0, 12, 20]
sage: f2 = Stream_integral(f, [-1, -1, -1], True)
sage: [f2.get_coefficient(i) for i in range(-1, 7)]
[0, -1, -1, -1/2, 0, 0, 1/5, 1/6]

is_nonzero()

Return True if and only if this stream is known to be non-zero.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_function, Stream_integral
sage: f = Stream_function(lambda n: 2*n, True, 1)
sage: f[1]
2
sage: f.is_nonzero()
True
sage: Stream_integral(f, [0], True).is_nonzero()
True
sage: f = Stream_function(lambda n: 0, False, 1)
sage: Stream_integral(f, [0, 0, 0], False).is_nonzero()
False
sage: Stream_integral(f, [0, 2], False).is_nonzero()
True

class sage.data_structures.stream.Stream_iterator(iter, approximate_order, true_order=False)

Bases: Stream_inexact

Class that creates a stream from an iterator.

INPUT:

• iter – a function that generates the coefficients of the stream

• approximate_order – integer; a lower bound for the order of the stream

Instances of this class are always dense.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_iterator
sage: f = Stream_iterator(iter(NonNegativeIntegers()), 0)
sage: [f[i] for i in range(10)]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

sage: f = Stream_iterator(iter(NonNegativeIntegers()), 1)
sage: [f[i] for i in range(10)]
[0, 0, 1, 2, 3, 4, 5, 6, 7, 8]

class sage.data_structures.stream.Stream_lmul(series, scalar, is_sparse)

Bases: Stream_scalar

Operator for multiplying a coefficient stream with a scalar as self * scalar.

INPUT:

• series – a Stream

• scalar – a non-zero, non-one scalar

EXAMPLES:

sage: # needs sage.modules
sage: from sage.data_structures.stream import (Stream_lmul, Stream_function)
sage: W = algebras.DifferentialWeyl(QQ, names=('x',))
sage: x, dx = W.gens()
sage: f = Stream_function(lambda n: x^n, True, 1)
sage: g = Stream_lmul(f, dx, True)
sage: [g[i] for i in range(5)]
[0, x*dx, x^2*dx, x^3*dx, x^4*dx]

get_coefficient(n)

Return the n-th coefficient of self.

INPUT:

• n – integer; the degree for the coefficient

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_lmul, Stream_function)
sage: f = Stream_function(lambda n: n, True, 1)
sage: g = Stream_lmul(f, 3, True)
sage: g.get_coefficient(5)
15
sage: [g.get_coefficient(i) for i in range(10)]
[0, 3, 6, 9, 12, 15, 18, 21, 24, 27]

class sage.data_structures.stream.Stream_map_coefficients(series, function, is_sparse, approximate_order=None, true_order=False)

Bases: Stream_unary

The stream with function applied to each non-zero coefficient of series.

INPUT:

• series – a Stream

• function – a function that modifies the elements of the stream

Note

We assume for equality that function is a function in the mathematical sense.

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_map_coefficients, Stream_function)
sage: f = Stream_function(lambda n: 1, True, 1)
sage: g = Stream_map_coefficients(f, lambda n: -n, True)
sage: [g[i] for i in range(10)]
[0, -1, -1, -1, -1, -1, -1, -1, -1, -1]

get_coefficient(n)

Return the n-th coefficient of self.

INPUT:

• n – integer; the degree for the coefficient

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_map_coefficients, Stream_function)
sage: f = Stream_function(lambda n: n, True, -1)
sage: g = Stream_map_coefficients(f, lambda n: n^2 + 1, True)
sage: g.get_coefficient(5)
26
sage: [g.get_coefficient(i) for i in range(-1, 10)]
[2, 0, 2, 5, 10, 17, 26, 37, 50, 65, 82]

sage: R.<x,y> = ZZ[]
sage: f = Stream_function(lambda n: n, True, -1)
sage: g = Stream_map_coefficients(f, lambda n: R(n).degree() + 1, True)
sage: [g.get_coefficient(i) for i in range(-1, 3)]
[1, 0, 1, 1]

class sage.data_structures.stream.Stream_neg(series, is_sparse)

Bases: Stream_unary

Operator for negative of the stream.

INPUT:

• series – a Stream

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_neg, Stream_function)
sage: f = Stream_function(lambda n: 1, True, 1)
sage: g = Stream_neg(f, True)
sage: [g[i] for i in range(10)]
[0, -1, -1, -1, -1, -1, -1, -1, -1, -1]

get_coefficient(n)

Return the n-th coefficient of self.

INPUT:

• n – integer; the degree for the coefficient

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_neg, Stream_function)
sage: f = Stream_function(lambda n: n, True, 1)
sage: g = Stream_neg(f, True)
sage: g.get_coefficient(5)
-5
sage: [g.get_coefficient(i) for i in range(10)]
[0, -1, -2, -3, -4, -5, -6, -7, -8, -9]

is_nonzero()

Return True if and only if this stream is known to be non-zero.

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_neg, Stream_function)
sage: f = Stream_function(lambda n: n, True, 1)
sage: g = Stream_neg(f, True)
sage: g.is_nonzero()
False

sage: from sage.data_structures.stream import Stream_cauchy_invert
sage: fi = Stream_cauchy_invert(f)
sage: g = Stream_neg(fi, True)
sage: g.is_nonzero()
True

class sage.data_structures.stream.Stream_plethysm(f, g, is_sparse, p, ring=None, include=None, exclude=None)

Bases: Stream_binary

Return the plethysm of f composed by g.

This is the plethysm \(f \circ g = f(g)\) when \(g\) is an element of a ring of symmetric functions.

INPUT:

• f – a Stream

• g – a Stream with positive order, unless f is of Stream_exact.

• p – the ring of powersum symmetric functions containing g

• ring (optional, default None) – the ring the result should be in, by default p

• include – a list of variables to be treated as degree one elements instead of the default degree one elements

• exclude – a list of variables to be excluded from the default degree one elements

EXAMPLES:

sage: # needs sage.modules
sage: from sage.data_structures.stream import Stream_function, Stream_plethysm
sage: s = SymmetricFunctions(QQ).s()
sage: p = SymmetricFunctions(QQ).p()
sage: f = Stream_function(lambda n: s[n], True, 1)
sage: g = Stream_function(lambda n: s[[1]*n], True, 1)
sage: h = Stream_plethysm(f, g, True, p, s)
sage: [h[i] for i in range(5)]
[0,
 s[1],
 s[1, 1] + s[2],
 2*s[1, 1, 1] + s[2, 1] + s[3],
 3*s[1, 1, 1, 1] + 2*s[2, 1, 1] + s[2, 2] + s[3, 1] + s[4]]
sage: u = Stream_plethysm(g, f, True, p, s)
sage: [u[i] for i in range(5)]
[0,
 s[1],
 s[1, 1] + s[2],
 s[1, 1, 1] + s[2, 1] + 2*s[3],
 s[1, 1, 1, 1] + s[2, 1, 1] + 3*s[3, 1] + 2*s[4]]

This class also handles the plethysm of an exact stream with a stream of order \(0\):

sage: # needs sage.modules
sage: from sage.data_structures.stream import Stream_exact
sage: f = Stream_exact([s[1]], order=1)
sage: g = Stream_function(lambda n: s[n], True, 0)
sage: r = Stream_plethysm(f, g, True, p, s)
sage: [r[n] for n in range(3)]
[s[], s[1], s[2]]

compute_product(n, la)

Compute the product p[la](self._right) in degree n.

EXAMPLES:

sage: # needs sage.modules
sage: from sage.data_structures.stream import Stream_plethysm, Stream_exact, Stream_function, Stream_zero
sage: s = SymmetricFunctions(QQ).s()
sage: p = SymmetricFunctions(QQ).p()
sage: f = Stream_exact([1]) # irrelevant for this test
sage: g = Stream_exact([s[2], s[3]], 0, 4, 2)
sage: h = Stream_plethysm(f, g, True, p)
sage: A = h.compute_product(7, Partition([2, 1])); A
1/12*p[2, 2, 1, 1, 1] + 1/4*p[2, 2, 2, 1] + 1/6*p[3, 2, 2]
 + 1/12*p[4, 1, 1, 1] + 1/4*p[4, 2, 1] + 1/6*p[4, 3]
sage: A == p[2, 1](s[2] + s[3]).homogeneous_component(7)
True

sage: # needs sage.modules
sage: p2 = tensor([p, p])
sage: f = Stream_exact([1]) # irrelevant for this test
sage: g = Stream_function(lambda n: sum(tensor([p[k], p[n-k]])
....:                                   for k in range(n+1)), True, 1)
sage: h = Stream_plethysm(f, g, True, p2)
sage: A = h.compute_product(7, Partition([2, 1]))
sage: B = p[2, 1](sum(g[n] for n in range(7)))
sage: B = p2.element_class(p2, {m: c for m, c in B
....:                           if sum(mu.size() for mu in m) == 7})
sage: A == B
True

sage: # needs sage.modules
sage: f = Stream_exact([1]) # irrelevant for this test
sage: g = Stream_function(lambda n: s[n], True, 0)
sage: h = Stream_plethysm(f, g, True, p)
sage: B = p[2, 2, 1](sum(p(s[i]) for i in range(7)))
sage: all(h.compute_product(k, Partition([2, 2, 1]))
....:      == B.restrict_degree(k) for k in range(7))
True

get_coefficient(n)

Return the n-th coefficient of self.

INPUT:

• n – integer; the degree for the coefficient

EXAMPLES:

sage: # needs sage.modules
sage: from sage.data_structures.stream import Stream_function, Stream_plethysm
sage: s = SymmetricFunctions(QQ).s()
sage: p = SymmetricFunctions(QQ).p()
sage: f = Stream_function(lambda n: s[n], True, 1)
sage: g = Stream_function(lambda n: s[[1]*n], True, 1)
sage: h = Stream_plethysm(f, g, True, p)
sage: s(h.get_coefficient(5))
4*s[1, 1, 1, 1, 1] + 4*s[2, 1, 1, 1] + 2*s[2, 2, 1] + 2*s[3, 1, 1] + s[3, 2] + s[4, 1] + s[5]
sage: [s(h.get_coefficient(i)) for i in range(6)]
[0,
 s[1],
 s[1, 1] + s[2],
 2*s[1, 1, 1] + s[2, 1] + s[3],
 3*s[1, 1, 1, 1] + 2*s[2, 1, 1] + s[2, 2] + s[3, 1] + s[4],
 4*s[1, 1, 1, 1, 1] + 4*s[2, 1, 1, 1] + 2*s[2, 2, 1] + 2*s[3, 1, 1] + s[3, 2] + s[4, 1] + s[5]]

stretched_power_restrict_degree(i, m, d)

Return the degree d*i part of p([i]*m)(g) in terms of self._basis.

INPUT:

• i, m – positive integers

• d – integer

EXAMPLES:

sage: # needs sage.modules
sage: from sage.data_structures.stream import Stream_plethysm, Stream_exact, Stream_function, Stream_zero
sage: s = SymmetricFunctions(QQ).s()
sage: p = SymmetricFunctions(QQ).p()
sage: f = Stream_exact([1]) # irrelevant for this test
sage: g = Stream_exact([s[2], s[3]], 0, 4, 2)
sage: h = Stream_plethysm(f, g, True, p)
sage: A = h.stretched_power_restrict_degree(2, 3, 6)
sage: A == p[2,2,2](s[2] + s[3]).homogeneous_component(12)
True

sage: # needs sage.modules
sage: p2 = tensor([p, p])
sage: f = Stream_exact([1]) # irrelevant for this test
sage: g = Stream_function(lambda n: sum(tensor([p[k], p[n-k]])
....:                                   for k in range(n+1)), True, 1)
sage: h = Stream_plethysm(f, g, True, p2)
sage: A = h.stretched_power_restrict_degree(2, 3, 6)
sage: B = p[2,2,2](sum(g[n] for n in range(7)))     # long time
sage: B = p2.element_class(p2, {m: c for m, c in B  # long time
....:                           if sum(mu.size() for mu in m) == 12})
sage: A == B                        # long time
True

class sage.data_structures.stream.Stream_rmul(series, scalar, is_sparse)

Bases: Stream_scalar

Operator for multiplying a coefficient stream with a scalar as scalar * self.

INPUT:

• series – a Stream

• scalar – a non-zero, non-one scalar

EXAMPLES:

sage: # needs sage.modules
sage: from sage.data_structures.stream import (Stream_rmul, Stream_function)
sage: W = algebras.DifferentialWeyl(QQ, names=('x',))
sage: x, dx = W.gens()
sage: f = Stream_function(lambda n: x^n, True, 1)
sage: g = Stream_rmul(f, dx, True)
sage: [g[i] for i in range(5)]
[0, x*dx + 1, x^2*dx + 2*x, x^3*dx + 3*x^2, x^4*dx + 4*x^3]

get_coefficient(n)

Return the n-th coefficient of self.

INPUT:

• n – integer; the degree for the coefficient

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_rmul, Stream_function)
sage: f = Stream_function(lambda n: n, True, 1)
sage: g = Stream_rmul(f, 3, True)
sage: g.get_coefficient(5)
15
sage: [g.get_coefficient(i) for i in range(10)]
[0, 3, 6, 9, 12, 15, 18, 21, 24, 27]

class sage.data_structures.stream.Stream_scalar(series, scalar, is_sparse)

Bases: Stream_unary

Base class for operators multiplying a coefficient stream by a scalar.

INPUT:

• series – a Stream

• scalar – a non-zero, non-one scalar

• is_sparse – boolean

is_nonzero()

Return True if and only if this stream is known to be non-zero.

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_rmul, Stream_function)
sage: f = Stream_function(lambda n: n, True, 1)
sage: g = Stream_rmul(f, 2, True)
sage: g.is_nonzero()
False

sage: from sage.data_structures.stream import Stream_cauchy_invert
sage: fi = Stream_cauchy_invert(f)
sage: g = Stream_rmul(fi, 2, True)
sage: g.is_nonzero()
True

class sage.data_structures.stream.Stream_shift(series, shift)

Bases: Stream

Operator for shifting a non-zero, non-exact stream.

Instances of this class share the cache with its input stream.

INPUT:

• series – a Stream

• shift – an integer

is_nonzero()

Return True if and only if this stream is known to be non-zero.

An assumption of this class is that it is non-zero.

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_cauchy_invert, Stream_function)
sage: f = Stream_function(lambda n: n^2, False, 1)
sage: g = Stream_cauchy_invert(f)
sage: g.is_nonzero()
True

is_uninitialized()

Return True if self is an uninitialized stream.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_uninitialized, Stream_shift
sage: C = Stream_uninitialized(0)
sage: S = Stream_shift(C, 5)
sage: S.is_uninitialized()
True

order()

Return the order of self, which is the minimum index n such that self[n] is non-zero.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_function, Stream_shift
sage: s = Stream_shift(Stream_function(lambda n: n, True, 0), 2)
sage: s.order()
3

class sage.data_structures.stream.Stream_sub(left, right, is_sparse)

Bases: Stream_binary

Operator for subtraction of two coefficient streams.

INPUT:

• left – Stream of coefficients on the left side of the operator

• right – Stream of coefficients on the right side of the operator

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_sub, Stream_function)
sage: f = Stream_function(lambda n: n, True, 0)
sage: g = Stream_function(lambda n: 1, True, 0)
sage: h = Stream_sub(f, g, True)
sage: [h[i] for i in range(10)]
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8]
sage: u = Stream_sub(g, f, True)
sage: [u[i] for i in range(10)]
[1, 0, -1, -2, -3, -4, -5, -6, -7, -8]

get_coefficient(n)

Return the n-th coefficient of self.

INPUT:

• n – integer; the degree for the coefficient

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_function, Stream_sub)
sage: f = Stream_function(lambda n: n, True, 0)
sage: g = Stream_function(lambda n: n^2, True, 0)
sage: h = Stream_sub(f, g, True)
sage: h.get_coefficient(5)
-20
sage: [h.get_coefficient(i) for i in range(10)]
[0, 0, -2, -6, -12, -20, -30, -42, -56, -72]

class sage.data_structures.stream.Stream_taylor(function, is_sparse)

Bases: Stream_inexact

Class that returns a stream for the Taylor series of a function.

INPUT:

• function – a function that has a derivative method and takes a single input

• is_sparse – boolean; specifies whether the stream is sparse

EXAMPLES:

sage: from sage.data_structures.stream import Stream_taylor
sage: g(x) = sin(x)
sage: f = Stream_taylor(g, False)
sage: f[3]
-1/6
sage: [f[i] for i in range(10)]
[0, 1, 0, -1/6, 0, 1/120, 0, -1/5040, 0, 1/362880]

sage: g(y) = cos(y)
sage: f = Stream_taylor(g, False)
sage: n = f.iterate_coefficients()
sage: [next(n) for _ in range(10)]
[1, 0, -1/2, 0, 1/24, 0, -1/720, 0, 1/40320, 0]

sage: g(z) = 1 / (1 - 2*z)
sage: f = Stream_taylor(g, True)
sage: [f[i] for i in range(4)]
[1, 2, 4, 8]

get_coefficient(n)

Return the n-th coefficient of self.

INPUT:

• n – integer; the degree for the coefficient

EXAMPLES:

sage: from sage.data_structures.stream import Stream_taylor
sage: g(x) = exp(x)
sage: f = Stream_taylor(g, True)
sage: f.get_coefficient(5)
1/120

sage: from sage.data_structures.stream import Stream_taylor
sage: y = SR.var('y')
sage: f = Stream_taylor(sin(y), True)
sage: f.get_coefficient(0)
0
sage: f.get_coefficient(5)
1/120

iterate_coefficients()

A generator for the coefficients of self.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_taylor
sage: x = polygen(QQ, 'x')
sage: f = Stream_taylor(x^3, False)
sage: it = f.iterate_coefficients()
sage: [next(it) for _ in range(10)]
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0]

sage: y = SR.var('y')
sage: f = Stream_taylor(y^3, False)
sage: it = f.iterate_coefficients()
sage: [next(it) for _ in range(10)]
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0]

class sage.data_structures.stream.Stream_truncated(series, shift, minimal_valuation)

Bases: Stream_unary

Operator for shifting a non-zero, non-exact stream that has been shifted below its minimal valuation.

Instances of this class share the cache with its input stream.

INPUT:

• series – a Stream_inexact

• shift – an integer

• minimal_valuation – an integer; this is also the approximate order

is_nonzero()

Return True if and only if this stream is known to be non-zero.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_function, Stream_truncated
sage: def fun(n): return 1 if ZZ(n).is_power_of(2) else 0
sage: f = Stream_function(fun, False, 0)
sage: [f[i] for i in range(0, 4)]
[0, 1, 1, 0]
sage: f._cache
[1, 1, 0]
sage: s = Stream_truncated(f, -5, 0)
sage: s.is_nonzero()
False
sage: [f[i] for i in range(7,10)]  # updates the cache of s
[0, 1, 0]
sage: s.is_nonzero()
True

sage: f = Stream_function(fun, True, 0)
sage: [f[i] for i in range(0, 4)]
[0, 1, 1, 0]
sage: f._cache
{1: 1, 2: 1, 3: 0}
sage: s = Stream_truncated(f, -5, 0)
sage: s.is_nonzero()
False
sage: [f[i] for i in range(7,10)]  # updates the cache of s
[0, 1, 0]
sage: s.is_nonzero()
True

order()

Return the order of self, which is the minimum index n such that self[n] is non-zero.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_function, Stream_truncated
sage: def fun(n): return 1 if ZZ(n).is_power_of(2) else 0
sage: s = Stream_truncated(Stream_function(fun, True, 0), -5, 0)
sage: s.order()
3
sage: s = Stream_truncated(Stream_function(fun, False, 0), -5, 0)
sage: s.order()
3

Check that it also worked properly with the cache partially filled:

sage: f = Stream_function(fun, True, 0)
sage: dummy = [f[i] for i in range(10)]
sage: s = Stream_truncated(f, -5, 0)
sage: s.order()
3
sage: f = Stream_function(fun, False, 0)
sage: dummy = [f[i] for i in range(10)]
sage: s = Stream_truncated(f, -5, 0)
sage: s.order()
3

class sage.data_structures.stream.Stream_unary(series, is_sparse, true_order=False)

Bases: Stream_inexact

Base class for unary operators on coefficient streams.

INPUT:

• series – Stream the operator acts on

• is_sparse – boolean

• true_order – boolean (default: False) if the approximate order is the actual order

EXAMPLES:

sage: from sage.data_structures.stream import (Stream_function, Stream_cauchy_invert, Stream_lmul)
sage: f = Stream_function(lambda n: 2*n, False, 1)
sage: g = Stream_cauchy_invert(f)
sage: [g[i] for i in range(10)]
[-1, 1/2, 0, 0, 0, 0, 0, 0, 0, 0]
sage: g = Stream_lmul(f, 2, True)
sage: [g[i] for i in range(10)]
[0, 4, 8, 12, 16, 20, 24, 28, 32, 36]

is_uninitialized()

Return True if self is an uninitialized stream.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_uninitialized, Stream_unary
sage: C = Stream_uninitialized(0)
sage: M = Stream_unary(C, True)
sage: M.is_uninitialized()
True

class sage.data_structures.stream.Stream_uninitialized(approximate_order, true_order=False)

Bases: Stream_inexact

Coefficient stream for an uninitialized series.

INPUT:

• approximate_order – integer; a lower bound for the order of the stream

Instances of this class are always dense.

Todo

Should instances of this class share the cache with its _target?

EXAMPLES:

sage: from sage.data_structures.stream import Stream_uninitialized
sage: from sage.data_structures.stream import Stream_exact
sage: one = Stream_exact([1])
sage: C = Stream_uninitialized(0)
sage: C._target
sage: C._target = one
sage: C[4]
0

is_uninitialized()

Return True if self is an uninitialized stream.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_uninitialized
sage: C = Stream_uninitialized(0)
sage: C.is_uninitialized()
True

A more subtle uninitialized series:

sage: L.<z> = LazyPowerSeriesRing(QQ)
sage: T = L.undefined(1)
sage: D = L.undefined(0)
sage: T.define(z * exp(T) * D)
sage: T._coeff_stream.is_uninitialized()
True

iterate_coefficients()

A generator for the coefficients of self.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_uninitialized
sage: from sage.data_structures.stream import Stream_exact
sage: z = Stream_exact([1], order=1)
sage: C = Stream_uninitialized(0)
sage: C._target
sage: C._target = z
sage: n = C.iterate_coefficients()
sage: [next(n) for _ in range(10)]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0]

class sage.data_structures.stream.Stream_zero

Bases: Stream

A coefficient stream that is exactly equal to zero.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_zero
sage: s = Stream_zero()
sage: s[5]
0

order()

Return the order of self, which is infinity.

EXAMPLES:

sage: from sage.data_structures.stream import Stream_zero
sage: s = Stream_zero()
sage: s.order()
+Infinity