Models of Walks in the Quarter Plane¶

File for the code for models of Walking in the quarter plane.

This method includes a generic class and a bunch of preset variables that can be used to work with the generating functions of Walks on the quarter plane.

In particular, lots of this methods works with the algebraic curve that the kernel polynomial defines for each model.

AUTHORS:

Antonio Jimenez-Pastor (2019-06-12): initial version

TODO:

Add EXAMPLES section

This package is under the terms of GNU General Public License version 3.

exception comb_walks.walkmodel.NonEllipticError¶

Bases: TypeError

Type error for showing a model is not elliptic

class comb_walks.walkmodel.WalkModel(*args, **kwds)¶

Bases: object

Class for representing a model of walks on the quarter plane.

A walk on the plane is a sequence of points \((P_0, P_1, \ldots) \in \mathbb{Z}^\mathbb{N}\) where, we say:

\(P_0\) is the origin of the walk.
If the sequence is finite, the last point \(P_n\) is the destiny and \(n\) is the length.
The \(i\).

Given a set \(S \subset \mathbb{Z}\), we can define a model of walks on the plane using the elements of \(S\) as valid steps. This means that the model allows finite walks where the steps of the walk are contained in \(S\).

In particular, models of this type have been widely studied when \(S \subset \{-1,0,1\}^2 \setminus \{(0,0)\}\), what are called small steps. Moreover, people is interested in the walks restricted to the quarter plane, i.e., all the points that are touched by a walk are in \(\mathbb{N}^2\).

Given a model, we can define the following generating function:

\[Q(x,y,t) = \sum_{i,j,n \geq 0} q_{i,j,n} x^iy^jt^n,\]

where \(q_{i,j,n}\) is the number of walks of length \(n\) that has origin at \((0,0)\) and destiny \((i,j)\) included in the model. This class provides several methods to understand this generating function.

To initialize a model, the step set \(S\) needs to be provided. For doing so, a list of valid steps have to be given by the user:

A valid step is any list of tuple with more than 1 element.
The first two elements will be the coordinates of the step.
If a third element is given, it will be the weight for that step. The default weight is \(1\).
If the list or tuple are longer, the other elements will be ignored.

If a invalid step is given, a Warning will pop up in the context of the warning system provided by the Python package “logging”. But the model will still be created without raising any error.

A(i, model='A')¶

Model to get the coefficients in \(y\) of the kernel equation.

For any walk model, we can write the affine kernel equation as

\[K(x,y,t) = A_{-1}(x,t) + A_0(x,t)y + A_1(x,t)y^2\]

This method return (in the corresponding model) the corresponding coefficient indicated by the input i. This value can be directly extracted from the kernel equation in the affine (A) and projective (P) models. For the Weierstrass model, we compute it on the affine model and compute its corresponding pullback.

For the affine case, the output involve the projective variable \(z\) and for the projective case, the output is homogeneous in \(x_0\) and \(x_1\).

INPUT:

i: the index of the coefficient we want to extract.
model: the model in which we want the coefficient.

B(i, model='A')¶

Model to get the coefficients in \(x\) of the kernel equation.

For any walk model, we can write the affine kernel equation as

\[K(x,y,t) = B_{-1}(y,t) + B_0(y,t)x + A_1(y,t)x^2\]

For the affine case, the output involve the projective variable \(z\) and for the projective case, the output is homogeneous in \(y_0\) and \(y_1\).

INPUT:

i: the index of the coefficient we want to extract.
model: the model in which we want the coefficient.

KR_f(var, model='A')¶

Method for computing the functions \(f_x\) and \(f_y\) from K.R.-2015

The kernel equation for the model looks like

\[\begin{split}\begin{array}{rcl} 0& = & Q(x,y,t)K(x,y,t) - \\ & & Q(x,0,t)K(x,0,t) - \\ & & Q(0,y,t)K(0,y,t) + \\ & & Q(0,0,t)K(0,0,t) + \\ & & xy \end{array}\end{split}\]

There are three pieces that are evaluations of the first term. We are focused now on the two middle terms, which are just the evaluations in \(y=0\) and \(x=0\) of the product of the generating function and the kernel (denoted by \(r_x\) and \(r_y\) respectively)

On the other hand, we have defined \(\tau\) a map that perform to ivolutions within the curve and that defines a point \(Q\) such that \(\tau(P) = P \oplus Q\) for all \(P\) in the curve. We can then study the behavior of the two sections with respect to this point:

\[\begin{split}\begin{array}{rcl} f_x & = & r_x \tau - r_x = y(x\iota_y - x)\\ f_y & = & r_y \tau - r_y = x(y\iota_x - y) \end{array}\end{split}\]

This method computes these functions and transform then into the required model.

REMARK:

this method, for variable \(2\), is equivalent to the method b() that we defined using the paper by Dreyfus, Hardoin, Roques and Singer.
this method, for variable \(1\), is related to the method b(), but now with a prefactor of i() for the variable \(x\)

INPUT:

var: the name or number of the varible. Any element which string is 'x' or 'y', or the numbers 1 (for \(x\)) and 2 (for \(y\)).
model: model of the curve we want the result. See method model() for further information.

OUTPUT:

sage: from comb_walks import *
sage: all(m.b(2)(x=x0/x1,y=y0/y1,z=1) == m.KR_f(2,'p') for m in AllModels if (not m.is_singular())) # long time
True
sage: all(m.b(1)(x=x0/x1,y=y0/y1) == pullback(m.iota(1,'p'))(m.KR_f(1, 'p')) for m in AllModels if (not m.is_singular())) # long time
True

KR_poles_f(var, model='P')¶

Method to get the poles of the functions \(f_x\) and \(f_y\).

This method computes the poles of the functions \(f_x\) and \(f_y\) defined in the method KR_f() using the expression from which we computed the functions.

This computations implies computing the intersection of the elliptic curve with the lines at infinity for \(x\) and \(y\), which may lead to some long computations and some algebraic extensions.

add_P(point, model='W')¶

Method to get the rational maps that add a point (in an elliptic curve).

This method computes the rational representation for adding a point on an elliptic curve. Since points on elliptic curves make an abelian group, we can, fixed \(P\) in the curve, we can take the map \(s_P\) defined with \(s_P(Q) = P+Q\).

It is known that these maps \(s_P\) are birrational maps. In fact, they are isomorphisms. This method just compute that rational map.

In the case of an elliptic curve in Weierstrass form, this map is geometrically seasy to compute and that is the method we use here. If the map required is not on the Weierstrass form, we translate into such model and then compute the map there.

This method is cached.

TODO:

Add INPUT, OUTPUT sections
Add examples

alg_extension(*args, **kwds)¶

Method to compute a uniform algebraic extension through all computations in the model.

This method allows the user to compute an algebraic extension with an uniform criteria through all computations. In this way, we will end up always with the smallest amount of extensions and, if possible, with the same extension through all the computations.

INPUT:

polynomial: a polynomial in one variable.
n: name for the algebraic extension. If not given, a standar decision for the name will be made.

ambient(model)¶

Method to get the current ambient space of the curve depending on the model required.

Since there are three different models, we have three different ambient spaces:

For model “A”: the space \(P^2\) with coordinates \((x:y:z)\).
For model “W”: the space \(P^2\) with coordinates \((u:v:w)\).
For model “P”: the space \(P^1\times P^1\) with two projective coordinates \((x0:x1,y0:y1)\)

Remark: this method will return a new element if we find a needed algebraic extension. Hence, the use of this method instead of a variable is highly recommended.

INPUT:

model: the type of ambient space we look. See method model() for further information.

EXAMPLES:

sage: from comb_walks.walkmodel import WalkModel; m = WalkModel.example_model()
sage: m.ambient(1)
Projective Space of dimension 2 over Fraction Field of Univariate Polynomial Ring in t over Rational Field
sage: m.ambient(2)
Projective Space of dimension 2 over Fraction Field of Univariate Polynomial Ring in t over Rational Field
sage: m.ambient(3)
Product of projective spaces P^1 x P^1 over Fraction Field of Univariate Polynomial Ring in t over Rational Field
sage: m.ambient(1).gens()
(x, y, z)
sage: m.ambient(2).gens()
(u, v, w)
sage: m.ambient(3).gens()
(x0, x1, y0, y1)
sage: all(m.ambient(el) == m.ambient(1) for el in [1,'xyz','xy','a','A'])
True
sage: all(m.ambient(el) == m.ambient(2) for el in [2, 'uvw', 'uv', 'w', 'weierstrass', 'W'])
True
sage: all(m.ambient(el) == m.ambient(3) for el in [3, 'x0x1y0y1', 'x0y0', 'p', 'projective', 'P'])
True

b(var)¶

EXAMPLES:

sage: class Foo:
....:     def __init__(self, x):
....:         self._x = x
....:     @cached_method
....:     def f(self,*args):
....:         return self._x^2
sage: a = Foo(2)
sage: a.f.cache
{}
sage: a.f()
4
sage: a.f.cache
{((), ()): 4}

base_ring()¶

Method to get the current base ring of the Walk Model.

This method returns the current coefficient ring where all the ambient spaces are based (see method ambient() for further information)

Remark: this method will return a new element if we find a needed algebraic extension. Hence, the use of this method instead of a variable is highly recommended.

change_ring(new_ring)¶

Method to change the base ring of the model.

This method changes the base ring of the model (see method base_ring() for further information) and it ensures that all the data that have been already computed using the previous ring is valid for this new base ring.

This requires that the pushout between the current ring and the new ring is exactly the new ring. Otherwise an error will be raised.

INPUT:

new_ring: the new base ring for all the elements of the model. This must be an extension of the current ring (see method base_ring()).

EXAMPLES:

sage: from comb_walks.walkmodel import WalkModel; m = WalkModel.example_model()
sage: t = m.pars(); F = m.base_ring()
sage: nF = FractionField(NumberField(QQ['i']('i^2+1'), 'i')[t])
sage: m.ring(1) # Basic ring
Multivariate Polynomial Ring in x, y, z over Fraction Field of Univariate Polynomial Ring in t over Rational Field
sage: m.change_ring(F) # Do nothing
sage: m.ring(1)
Multivariate Polynomial Ring in x, y, z over Fraction Field of Univariate Polynomial Ring in t over Rational Field
sage: m.change_ring(nF.base()) # Error because nF.base() is not a field
Traceback (most recent call last):
...
CoercionException: The new ring (...) is not a super ring for the current ring (...)
sage: m.change_ring(Integer(10)) # Error because 10 is not a ring
Traceback (most recent call last):
...
CoercionException: The argument (10) is not valid for pushout
    Reason: ...
sage: m.change_ring(nF) # Successfull change
sage: m.ring(1)
Multivariate Polynomial Ring in x, y, z over Fraction Field of Univariate Polynomial Ring in t over Number Field in i with defining polynomial i^2 + 1

curve(model='A')¶

Method to get the algebraic curve defined by the kernel function.

The kernel of a model (see kernel()) is a polynomial in the variables \(x\) and \(y\). This polynomial can be seen as the defining polynomial of a curve on the plane. This method returns the Sage structure for that particular curve.

Depending on how we homogenize the kernel function, we may end up with three different curves:

With model A: we homogenize with one variable \(z\).
With model P: we homogenize with two variables \(x \rightarrow x_0/x_1\) and \(y \rightarrow y_0/y_1\).
With model W: if the curve is elliptic, this provides the Weierstrass normal form of the curve.

INPUT:

model: it decides the curve is returned (see method model())

EXAMPLES:

sage: from comb_walks.walkmodel import *
sage: m = WalkModel(N,S,E,W); m.curve()
Closed subscheme of Projective Space of dimension 2 over Fraction Field of Univariate Polynomial Ring in t over Rational Field defined by:
  (-t)*x^2*y + (-t)*x*y^2 + x*y*z + (-t)*x*z^2 + (-t)*y*z^2
sage: m.curve('P')
Closed subscheme of Product of projective spaces P^1 x P^1 over Fraction Field of Univariate Polynomial Ring in t over Rational Field defined by:
  (-t)*x0*x1*y0^2 + (-t)*x0^2*y0*y1 + x0*x1*y0*y1 + (-t)*x1^2*y0*y1 + (-t)*x0*x1*y1^2
sage: all(m.curve(inp) is m.curve('A') for inp in [1,'xyz','xy','a','A'])
True
sage: all(m.curve(inp) is m.curve('P') for inp in [3, 'x0x1y0y1', 'x0y0', 'p', 'projective', 'P'])
True
sage: all(m.curve(inp) is m.curve('W') for inp in [2, 'uvw', 'uv', 'w', 'weierstrass', 'W'])
True

The Weierstrass model can not be computed for some models since they are not elliptic:

sage: m = NonEllipticC[0]; m.curve('W')
Traceback (most recent call last):
...
NonEllipticError: The kernel is not a elliptic curve --> No Weierstrass model

derivative(*args, **kwds)¶

Method for computing the derivative of a rational function over the curve.

This method takes a rational function on ‘x’ and ‘y’ coordinates and computes the corresponding derivation that commutes with the morphism ‘tau’. It is important that the function does not involve the variable ‘z’.

Vefore returning, it uses the equation of the curve to simplify the resulting function.

discriminant(var, model='A')¶

Method to compute the discriminant of the kernel with respect to one of its variables.

For any walk model, we can write the affine kernel equation as

\[K(x,y,t) = A_{-1}(x,t) + A_0(x,t)y + A_1(x,t)y^2\]

\[K(x,y,t) = B_{-1}(y,t) + B_0(y,t)x + A_1(y,t)x^2\]

So we can look to the kernel equation as a degree 2 polynomial in \(x\) or a degree 2 polynomial in \(y\). This method computes the discriminant of the kernel either in \(x\) or \(y\) leading to a polynomial in the other variable which roots are the points where the involution methods \(\iota_1\) and \(\iota_2\) (see method i()) have fixed points.

It is pretty obvious that the kernel curve is smooth (i.e., elliptic – is_elliptic()) if there is no point that is fixed by both \(\iota_1\) and \(\iota_2\), i.e., for any zeros \(P_x \in \mathbb{P}\) of the discriminant w.r.t. \(y\) and \(Q_y \in \mathbb{P}\) of the discriminant w.r.t. \(x\), we have

\[K(P_x, Q_y, t) \neq 0\]

Which means that the point \((P_x,Q_y)\) is not in the kernel curve.

TODO:

Add INPUT OUTPUT sections
Add tests and examples

dx()¶

Method to compute the 1-form \(dx\) w.r.t the holomorphic form.

On an elliptic curve there is a unique (up to constant) holomorphic form \(\omega\) (see method holomorphic_form()). Then all 1-forms can be written as \(\omega\) multiplied by a rational function. This method computes

\[dx = F \omega\]

and returns the rational function \(F\) that represents \(dx\) w.r.t. \(\omega\).

OUTPUT:

The rational function \(F\) such that \(dx = F\omega\).
If the kernel curve is not elliptic (see method is_elliptic()) a NonEllipticError is raised.

EXAMPLES:

sage: from comb_walks import *
sage: m = NonEllipticC[0]; m.dx()
Traceback (most recent call last):
...
NonEllipticError: The kernel is not a elliptic curve --> No Weierstrass model

TODO:

Increase the number of tests

dx_dy()¶

Method that computes the relation between differentials on the Affine Curve \(dx/dy\).

See method derivative() for further information about the derivation in the kernel curve (see method curve()).

For any algebraic curve \(K(x,y) = 0\), we do not only have a relation for the points but also an inherited relation between 1-forms:

\[K_x(x,y) dx + K_y(x,y)dy = 0\]

Then, for any curve we can compute the derivation of \(x\) w.r.t. \(y\), i.e., the quotient \(dx/dy\):

\[\frac{dx}{dy} = - \frac{K_y(x,y)}{K_x(x,y)}\]

EXAMPLES:

sage: from comb_walks import *
sage: WalkModel.example_model().dx_dy()
(t*x^2 + 2*t*x*y - x + t)/((-2*t)*x*y + (-t)*y^2 + y - t)

This quotient can also be computed even when the model is not elliptic:

sage: NonEllipticC[0].dx_dy()
(2*t*x*y - x + 2*t*y)/((-t)*y^2 + (-2*t)*x + y)

This method always returns the multiplicative inverse of the method dy_dx():

sage: all(1/m.dx_dy() == m.dy_dx() for m in AllModels)
True

dy()¶

Method to compute the 1-form \(dy\) w.r.t the holomorphic form.

\[dy = G \omega\]

and returns the rational function \(G\) that represents \(dy\) w.r.t. \(\omega\).

OUTPUT:

The rational function \(G\) such that \(dy = G\omega\).
If the kernel curve is not elliptic (see method is_elliptic()) a NonEllipticError is raised.

EXAMPLES:

sage: from comb_walks import *
sage: m = NonEllipticC[0]; m.dy()
Traceback (most recent call last):
...
NonEllipticError: The kernel is not a elliptic curve --> No Weierstrass model

TODO:

Increase the number of tests

dy_dx()¶

Method that computes the relation between differentials on the Affine Curve \(dy/dx\).

See method derivative() for further information about the derivation in the kernel curve (see method curve()).

For any algebraic curve \(K(x,y) = 0\), we do not only have a relation for the points but also an inherited relation between 1-forms:

\[K_x(x,y) dx + K_y(x,y)dy = 0\]

Then, for any curve we can compute the derivation of \(y\) w.r.t. \(x\), i.e., the quotient \(dy/dx\):

\[\frac{dy}{dx} = - \frac{K_x(x,y)}{K_y(x,y)}\]

EXAMPLES:

sage: from comb_walks import *
sage: WalkModel.example_model().dy_dx()
(2*t*x*y + t*y^2 - y + t)/((-t)*x^2 + (-2*t)*x*y + x - t)

This quotient can also be computed even when the model is not elliptic:

sage: NonEllipticC[0].dy_dx()
(t*y^2 + 2*t*x - y)/((-2*t)*x*y + x + (-2*t)*y)

eisenstein(invariant='F')¶

Method to compute the Eisenstein’s invariants of the curve.

There are three different invariants for the kernel curve called Eisenstein’s invariants. These invariants only depends on the kernel function (see method kernel()) and characterize esily whether the curve is elliptic or not (see method is_elliptic()).

INPUT:

invariant: the user has to provide its name (i.e., D, E or F) or a number (resp. 1, 2 or 3).

OUPUT:

The corresponding invariant in the corresponding field.

TODO:

Add INPUT OUTPUT sections

static example_model()¶

Static method for getting an example of WalkModel used for several tests.

The model returned is always the same (equivalent to RookModel) with four steps (east, north, west and south) and the name Example Model.

EXAMPLE:

sage: from comb_walks.walkmodel import WalkModel
sage: WalkModel.example_model()
Walk Model (Example Model)
sage: WalkModel.example_model().steps()
[((1, 0), 1), ((0, 1), 1), ((-1, 0), 1), ((0, -1), 1)]

g2()¶

Method to check get the \(g_2\) invariant of the curve.

This method compute the corresponding invariant of the curve. If the curve is elliptic (see method is_elliptic()) then this invariant is the constant coefficient in the Weierstrass form of the curve.

TODO:

Add INPUT OUTPUT sections
Add tests and examples

g3()¶

Method to check get the \(g_3\) invariant of the curve.

TODO:

Add INPUT OUTPUT sections
Add tests and examples

get_point_tau(model='P')¶

Method to compute a point \(Q\) that represents the map \(\tau\).

In the particular case where the kernel curve is elliptic (see method is_elliptic()) then the map \(\tau\) (see method tau()) can be seen as the addition of a point \(Q\) from the elliptic curve:

\[\tau(P) = P \oplus Q\]

This method computes this point \(Q\). For doing so, this method computes \(\tau(O)\) where \(O\) is the neutral point of the elliptic curve.

INPUT:

model: model of the elliptic curve we work on. See method model() for further information.

OUTPUT:

The point \(Q\) such that for all other points in the kernel curve \(P\), \(\tau(P) = P \oplus Q\).
If the model is not elliptic, a NonEllipticError is raised.

TODO:

Add examples

get_unweighted_model()¶

Method that creates the unweighted equivalent model

This method creates a new model for walks in the quarter plane where we remove all the weights and stablish them to 1.

higher_polar_part(func, point, model='P')¶

Method to compute the higher polar part of a rational function at a point.

Given an elliptic curve \(E\) and a point \(P \in E\), there are (using Riemman-Roch theorem) rational functions over \(E\) that have poles only at \(P\) with order \(n\) and are regular elsewhere for all \(n \geq 2\). Hence, we can distinguish all the polar part of any function up to the order 2.

The higher polar part of \(f \in \mathbb{C}(E)\) at a point \(P\) is a rational function \(g\) such that \(g\) only has poles at \(P\) and \(\operatorname{ord}_P(f-g) \geq -1\). See method only_pole_point() to see how to compute the basic pieces of \(g\). With those basic pieces, we can use linear algebra to compute \(g\) completely.

WARNING: The method catched the result internally.

INPUT:

func: rational function we want to analyze.
point: point on the curve to compute the higher polar part.
model: the model we are working with. See method model() for further information.

OUTPUT:

This method returns a rational function. The method comb_walks.alggeo.simplify_rational_variety() will be applied before returning, so some kind of cannonical output is expected.

TODO:

Add examples and tests.

holomorphic_form(model='A')¶

Method that computes the _unique_ holomorphic form on the elliptic curve.

This method computes a holomorphic differential form on the elliptic curve defined in the model. On an elliptic curve there is a unique (up to constant) holomorphic form. If the curve is on the Weierstrass model, such form is \((du)/v\). This form defines a unique derivation on the elliptic curve that allows to compute some differential operator that, in the end, will commute with the isomorpism \(\tau\) defined by the method tau().

For the model in the coordinates \(x\), \(y\) and \(z\) (see method model() for more information) this form can be computed quickly since we have \(u = u(x,y,z)\), \(v = v(x,y,z)\) and then

\[du = u_x dx + u_y dy + u_z dz.\]

INPUT:

model: the model we want to compute the holomorphic form (see model()). The double projective model (i.e., P) is not implemented.

OUTPUT:

A pair \((f,g)\) rational function on the model given such that the holomorphic form is \(\omega = fdx + gdy\) where \(x\) and \(y\) are the two affine variables of the model.
If the kernel curve is not elliptic (see method is_elliptic()) a NonEllipticError is raised.

EXAMPLES:

sage: from comb_walks import *
sage: m = NonEllipticC[0]; m.holomorphic_form()
Traceback (most recent call last):
...
NonEllipticError: The kernel is not a elliptic curve --> No Weierstrass model

TODO:

Increase the number of tests

intersection(*args, **kwds)¶

inv_P(point, model='W')¶

Method to compute the elliptic inverse of a point.

Points over elliptic curves make an abelian group. This method receives a point on the elliptic curve for the model and compute its additional inverse, i.e., given \(P\) in the curve, we compute \(Q\) such that \(P+Q = O\).

In the particular case of the Weierstrass model, this inverse is easy to compute:

If \(P = (0:1:0)\), then \(P = O\) and we return \(O\).
If \(P = (a:b:1)\), then \(Q = (a:-b:1)\).

This method is cached.

TODO:

Add INPUT, OUTPUT sections
Add examples

iota(var, model='A')¶

Method that build the involutions associated to the kernel curve.

Since, for any model with small steps we can write the kernel equation in the following forms:

\[K(x,y) = A_{-1}(x) + A_0(x)y + A_1(x)y^2 = B_{-1}(y) + B_0(y)*x + B_1(y)*x^2\]

Then we have that, fixed \(x_0\), we can compute always two values for \(y\) that are on the curve and, in the same way, fixed \(y_0\) we can compute two possible values of \(x\) for getting point on the curve.

This method, given one of the variables, returns the involution on the curve that fix such variable and swap between the two possible values for the other variable.

This involutions are always of order two. It is interesting to remark that the computation of such involution is slightly different for the affine model and the projective model. However its computation over the Weierstrass model is just a pullback from the affine case.

INPUT:

var: the variable we are fixing. This input can be given as "x" or 1 for the first variable and "y" or 2 for the second variable.
model: model of the elliptic curve we work on. See method model() for further information.

OUTPUT:

The corresponding involution in the required representation.
If the model is not elliptic (see method is_elliptic()) and the Wierstrass representation is required a NonEllipticError is raised.

TODO:

Add examples.

is_elliptic()¶

Method to check wether the kernel curve is elliptic or not.

This method compute the corresponding invariant of the curve and, due to its form, being elliptic is equivalent to have a non-zero invariant.

TODO:

Add INPUT OUTPUT sections
Add tests and examples

is_multiple_pole(func, point, model='P')¶

Boolean for having a pole at a point of order higher than 1.

This method computes for a given point and function if it has a multiple pole at a particular point. See method comb_walks.alggeo.asymptotics() for further information.

INPUT:

func: rational function we want to check
point: point on the curve we want to check.
model: model we are working on. See method model() for further information.

OUTPUT:

True if the function described by func has a multiple pole at point. False otherwise.

TODO:

Add examples and tests

is_short_walk()¶

Method to check wether a model is of short steps or not.

A step \(s = (a,b)\) is said to be short if \(s \neq (0,0)\) and \(-1 \leq a,b \leq 1\). This method returns True if all the steps of the model are short and False otherwise.

EXAMPLES:

sage: from comb_walks.walkmodel import *
sage: m = WalkModel(N, S, [1,1,3]); m.is_short_walk()
True
sage: m = WalkModel(N, [2,1]); m.is_short_walk()
False

For all the examples considered in the papers of MBB and DHRS, they are of short steps:

sage: all(m.is_short_walk() for m in AllModels)
True

is_singular()¶

Method to check wether a model is singular or not.

A model of walks in the quarter plane is called singular if, for all the steps \(s = (a,b)\) of the model we have \(a+b \geq 0\). These models have the property that there are not walks on the quarter plane that comes back to the origin.

EXAMPLES:

sage: from comb_walks.walkmodel import *
sage: m = WalkModel(N,NW,NE,E,SE); m.is_singular()
True
sage: m = WalkModel([-2,2], [2, -2], N); m.is_singular()
True
sage: m = WalkModel([2,0], [2,1]); m.is_singular()
True
sage: m = WalkModel(N,S,E,W); m.is_singular()
False

For short walks, singular models are precisely those models which kernel equation generates a singular (i.e., non-elliptic) curve:

sage: all(m in NonEllipticC for m in AllModels if m.is_singular())
True

is_weighted()¶

Method to check wether a model is weighted or not.

We consider that a model is weighted if there are more than one value for the weight. This means that if all the steps have the same weight (even if such weight is not 1) the model is unweighted.

EXAMPLES:

sage: from comb_walks.walkmodel import *
sage: m = WalkModel(N,S,E,W); m.is_weighted()
False
sage: m = WalkModel(N,S, [1,1,2]); m.is_weighted()
True
sage: m = WalkModel([1,1,2], [0,1,2], [-1,1,2]); m.is_weighted()
False

All the models considered in the papers by BMM and DHRS are not weighted:

sage: all(not m.is_weighted() for m in AllModels)
True

itau(model='A')¶

Method to compute the map \(\tau^{-1}\) over the kernel curve.

The map \(\tau\) is the composition of the maps \(\iota_2 \circ \iota_1\) (see method iota()). This maps, when the kernel curve is smooth (see method is_singular()) is a birational map within the curve.

This map computes the map \(\tau^{-1} = \iota_1 \circ \iota_2\) and simplifies the result.

INPUT:

model: model of the elliptic curve we work on. See method model() for further information.

OUTPUT:

The map \(\tau^{-1}\) in the representation requested by the argument model.

EXAMPLES:

sage: from comb_walks import * 
sage: WalkModel.example_model().itau('p')
Scheme endomorphism of Closed subscheme of Product of projective spaces P^1 x P^1 ...
(-t)*x0*x1*y0^2 + (-t)*x0^2*y0*y1 + x0*x1*y0*y1 + (-t)*x1^2*y0*y1 + (-t)*x0*x1*y1^2
Defn: Defined by sending (x0 : x1 , y0 : y1) to 
        (-x1 : -x0 , -y1 : -y0).
sage: WalkModel.example_model().itau('a')
Scheme endomorphism of Closed subscheme of Projective Space of dimension 2 ...
(-t)*x^2*y + (-t)*x*y^2 + x*y*z + (-t)*x*z^2 + (-t)*y*z^2
Defn: Defined on coordinates by sending (x : y : z) to
        (-y*z : -x*z : -x*y)

If a model is not elliptic (see method is_elliptic()), the method raise a NonEllipticError when asking for Weierstrass representation:

sage: NonEllipticC[0].itau('p')
Scheme endomorphism of Closed subscheme of Product of projective spaces P^1 x P^1 ...
(-t)*x0*x1*y0^2 + (-t)*x1^2*y0^2 + x0*x1*y0*y1 + (-t)*x0^2*y1^2
Defn: Defined by sending (x0 : x1 , y0 : y1) to 
        (-x1*y0^2 : -x0*y1^2 , -x1^2*y0^3 : -x0*x1*y0^2*y1 - x0^2*y1^3).
sage: NonEllipticC[0].itau('w')
Traceback (most recent call last):
...
NonEllipticError: The kernel is not a elliptic curve --> No Weierstrass model

kernel(model='A')¶

Method that returns the associated kernel function for a Model.

In walks on the quarter plane, we can see that the step function (see method step()) allows to get a functional equation for the generating function \(Q(x,y,t)\). Let \(K(x,y,t) = xy(1-tS(x,y))\), then

In the case of short steps, this kernel can be computed as

\[K(x,y,t)Q(x,y,t) = K(0,y,t)Q(0,y,t) + K(x,0,t)Q(x,0,t) - K(0,0,t)Q(0,0,t)\]

It is interesting to remark that, when the walks have short steps, \(K(x,y,t)\) is a polynomial in \(x\), \(y\) and \(t\), so the evaluation with \(x=0\) and \(y=0\) in the previous equation always make sense.

This function \(K(x,y,t)\) is called the Kernel function for the model.

This polynomial can be interpreted as a defining equation for a plane curve (see method curve()), and it may have several representations depending on how we embed this affine curve in \(x\) and \(y\) into a projective space:

For the model “A”: the curve is embedded in \(P^2\), using coordinates \(x\), \(y\) and \(z\).
For the model “P”: the curve is embedded in \(P^1\times P^1\), using two projective coordinates.
For the model “W”: (only if the curve defined is elliptic) the curve is embedded in \(P^2\) and transformed into Weiertrass normal form.

INPUT:

model: it decides the kernel is returned (see method model())

EXAMPLES:

sage: from comb_walks.walkmodel import *
sage: m = WalkModel(N,S,E,W); m.kernel()
(-t)*x^2*y + (-t)*x*y^2 + x*y*z + (-t)*x*z^2 + (-t)*y*z^2
sage: m.kernel('P')
(-t)*x0*x1*y0^2 + (-t)*x0^2*y0*y1 + x0*x1*y0*y1 + (-t)*x1^2*y0*y1 + (-t)*x0*x1*y1^2
sage: m.kernel('W')
(-4)*u^3 + v^2*w + (4/3*t^4 - 4/3*t^2 + 1/12)*u*w^2 + (-8/27*t^6 - 5/9*t^4 + 1/9*t^2 - 1/216)*w^3
sage: all(m.kernel(inp) is m.kernel('A') for inp in [1,'xyz','xy','a','A'])
True
sage: all(m.kernel(inp) is m.kernel('P') for inp in [3, 'x0x1y0y1', 'x0y0', 'p', 'projective', 'P'])
True
sage: all(m.kernel(inp) is m.kernel('W') for inp in [2, 'uvw', 'uv', 'w', 'weierstrass', 'W'])
True

For all the models in the papers of BMM and DHRS, we can check the identity with the definition:

sage: all(m.kernel("A") == (x*y*(1-t*m.step()))(x=x/z, y=y/z).numerator() for m in AllModels) # long time
True
sage: all(m.kernel("P") == (x*y*(1-t*m.step()))(x=x0/x1, y=y0/y1).numerator() for m in AllModels) # long time
True

The Weierstras model can not be computed for some models since they are not elliptic:

sage: m = NonEllipticC[0]; m.kernel('W')
Traceback (most recent call last):
...
NonEllipticError: The kernel is not a elliptic curve --> No Weierstrass model

map(dom, codom)¶

Method to get the birrational map between the models for the kernel curve.

This method return a map etween different representations of the kernel curve. Since all these representacions are for the same curve, these maps are birational.

static model(model)¶

Static method for standarizing the input for deciding the model.

There are a total of three models available:

The basic model, with coordinates \(x\), \(y\), \(z\): 1, “xyz”, “xy”, “a”, “A”, “affine”
The Weierstrass model, with coordinates \(u\), \(v\), \(w\) (if the curve is elliptic): 2, “uvw”, “uv”, “w”, “weierstrass”, “W”
The doubly-projectivized model: when we projectivize \(x\) and \(y\) indepently: 3, “x0x1y0y1”, “x0y0”, “p”, “projective”, “P”

EXAMPLES:

sage: from comb_walks.walkmodel import *
sage: all(WalkModel.model(el) == "A" for el in [1,'xyz','xy','a','A','affine'])
True
sage: all(WalkModel.model(el) == "W" for el in [2, 'uvw', 'uv', 'w', 'weierstrass', 'W'])
True
sage: all(WalkModel.model(el) == "P" for el in [3, 'x0x1y0y1', 'x0y0', 'p', 'projective', 'P'])
True
sage: WalkModel.model("mymodel")
Traceback (most recent call last):
...
ValueError: Model not recognized

modulus()¶

Method to check get the modulus of the elliptic curve.

This method compute the corresponding invariant of the curve when the curve is elliptic (see method is_elliptic()).

TODO:

Add INPUT OUTPUT sections
Add tests and examples

name()¶

Method to recover the name for the model.

This method returns the name (if stablished) for this model. If there is no name set, then this method returns an empty string.

EXAMPLES:

sage: from comb_walks import *
sage: WalkModel.example_model().name()
Example Model
sage: AllModels[0]
FG-BMM-1.01

It is important to remark that having different names does not imply that the models are different:

sage: AllModels[0] == WalkModel.example_model()
True
sage: AllModels[0].name() == WalkModel.example_model().name()
False

neutral_point(model='A')¶

Method that return the neutral point of the elliptic curve.

The kernel function associated to some model of walks on the quarter plane usually defines an elliptic curve (see method curve()). It is well known that points on elliptic curves define an abelian group.

This method returns the neutral element of that group (if the curve is elliptic) or raise a TypeError in case the model does not define an elliptic curve.

In the Weierstrass model, the neutral point is always the point at the infinity line, i.e., \((0:1:0)\).
In other models, we compute the transformation from the Weierstrass model and the corresponding model and use the method comb_walks.alggeo.apply_map() on \((0:1:0)\) for getting the point.

INPUT:

model: it decides the point that is returned (see method model())

EXAMPLES:

sage: from comb_walks.walkmodel import *
sage: m = WalkModel(N,E,S,W); m.neutral_point()
(0 : 0 : 1)
sage: m.neutral_point('W')
(0 : 1 : 0)
sage: m.neutral_point('P')
(0 : 1 , 0 : 1)

We can check that all the models have the same neutral point in the Weierstrass model:

sage: all(m.curve('W')([0,1,0]) == m.neutral_point('W') for m in FiniteGroup + EllipticC) # long time
True

Not always the neutral point is the origin in the XY models:

sage: m = ModelDict["FG-BMM-2.5"]; m.neutral_point()
(0 : -1 : 1)
sage: m = ModelDict["wIB.1"]; m.neutral_point()
(-1 : 0 : 1)

Sometimes, this neutral point can also be an algebraic element over t:

sage: m = ModelDict["FG-BMM-1.02"]; m.neutral_point('P')
verbose 0 ...
(0 : 1 , -1/2*r : 1)

nsteps()¶

Method to get the total number of steps of the model.

This method returns the number of steps that are in the model. It is important to remark that we can not have repeated steps or that the weight does not change the counting of the steps.

EXAMPLES:

sage: from comb_walks.walkmodel import *
sage: m = WalkModel(N,S, [1,1,3]); m.nsteps()
3
sage: m = WalkModel(N,N,N,N,N); m.nsteps()
1
sage: m = WalkModel(N,NE,E,SE,S,SW,W,NW); m.nsteps()
8

only_pole_point(order, point, model='P')¶

Method to compute a function with a single pole of a particular order.

This method compute such function given the order of the pole and the point on the curve.

If \(E\) is in Weierstrass form:

\[E = \{(u:v:w)\ :\ 4u^3 - v^2w + Auw^2 + Bw^3 = 0\}\]

then at infinity (\(P = (0:1:0)\)), we know that \(u/w\) has a pole of order 2 and \(v/w\) has a pole of order 3. Hence for any \(n \geq 2\) we can write as \(n = 3 + 2m\) so the function \(vu^m\) has a unique pole of order \(n\) at \((0:1:0)\).

If \(E\) is in Weierstrass form and \(P \neq (0:1:0)\), there is a rational function \(\varphi\) such that \(\varphi(Q) = Q \ominus P\). If we consider now \(\varphi^*(g)\) for any rational function \(g \in \mathbb{C}(E)\), then \(\varphi^*(g)(P) = g(\varphi(P)) = g(0:1:0)\). This means that the behavior of \(\varphi^*(g)\) at \(P\) is the behavior of \(g\) at \((0:1:0)\). This means that:

\(\varphi^*(u/w)\) has a unique pole of order 2 at \(P\).
\(\varphi^*(v/w)\) has a unique pole of order 3 at \(P\).

Finally, if \(E\) is not in Weierstrass form, but we have a map \(\psi: E \rightarrow \tilde{E}\) to its Weierstrass form, then for any \(g \in \mathbb{C}(\tilde{E})\) and \(P \in E\), \(\psi^*(g)(P) = g(\psi(P))\). Hence, the behavior of \(\psi^*(g)\) at \(P\) is the same behavior as \(g\) has in \(\psi(P)\).

INPUT:

order: the order of the pole. It mast be a possitive integer greater than 1.
point: the point where we want to do the computations
model: the model to compute the function. See method model() for further information.

OUTPUT:

A rational function that has a unique pole at point of the given order.
If the model is not elliptic (see method is_elliptic()) the method raises a NonEllipticError.

TODO:

Add tests and examples

orbital_polar_part(func, poles, point, bound=5, w_orbits=False, model='P')¶

Method to compute the orbital polar part at one point.

This method computes the orbital polar part of a function at one point. In higher_polar_part() we describe what is on elliptic curves the higher polar part of a rational function \(f\). Now, given \(\tau\), these poles are grouped in orbits. The orbital polar part is defined as follows:

\[opol_P(f) = \sum_{k \in \mathbb{Z}} pol_P(\tau^{*n}(f)).\]

Intuitively, we move with \(\tau\) all the poles of the orbit of \(P\) to \(P\) and then we add all the polar behavior of the function.

Interestingly enough, if \(\tau(P) = Q\), then \(\tau(opol_P(f)) = opol_Q(f)\).

INPUT:

func: rational funtion we are analyzing.
poles: poles of func or \(\tau\)-orbits of the poles. See w_orbits.
point: point on the curve we are studying.
bound: in case it is needed, the bound for looking for \(\tau\)-orbits in the poles.
w_orbits: boolean argument deciding the type of the input of the poles. If set to True, the argument poles will be read as the output of the method orbits(), otherwise we use it as a list of poles of func and use the argument bound for building the corresponding \(\tau\)-orbits.
model: model of the elliptic curve we are working on. See method model() for further information.

TODO:

Add tests and examples

orbits(points, bound=10, model='P')¶

Method that looks \(\tau\)-orbits in a list of points up to some bound.

This method receives a list of points on the curve defined by the kernel function and tries to get which of them are related with the map \(\tau\). Since this can not always be done, we fixed a maximal bound to look for that relation.

INPUT:

points: list of point on the curve.
bound: maximal distance between the points.

OUTPUT:

A tuple (orbits, jumps) whew orbits is a list with all the orbits we have found and jumps a list of integers such that \tau^jumps[i][j](orbits[i][j]) == orbits[i][j+1].

TODO:

Add examples and tests

order_tau(bound=10)¶

Method to compute the order of the map \(\tau\).

See method tau() to se information about the map \(\tau\). This method tries to compute the order of the morphism \(\tau\) up to some bound order given by de user (\(10\) by default).

In the case that the kernel curve is elliptic (see method is_elliptic()), this order can be computed just taking a point on the curve (like the neutral point \(O\) - see method neutral_point()) and checking

\[\tau^n(O) = O\]

Otherwise, this method relies on the method order_morphism().

INPUT:

bound: the bound for looking for the order.

OUTPUT:

If the order of \(\tau\) is smaller or equal to bound then the method returns the order of \(\tau\).
Otherwise, the method returns \(\infty\).

EXAMPLES:

sage: comb_walks import * 
sage: WalkModel.example_model().order_tau()
2

The bound argument put a limit on where we look for the order:

sage: ModelDict["FG-BMM-3.2"].order_tau()
4
sage: ModelDict["FG-BMM-3.2"].order_tau(2)
Infinity

For the models in AllModels we can check all the orders of \(\tau\):

sage: all(m.order_tau() == 2 for m in AllModels if m.name().startswith("FG-BMM-1.")) # long time
True
sage: all(m.order_tau() == 3 for m in AllModels if m.name().startswith("FG-BMM-2.")) # long time
True
sage: ModelDict["FG-BMM-3.1"].order_tau()
4
sage: ModelDict["FG-BMM-3.2"].order_tau()
4
sage: all(m.order_tau() == Infinity for m in AllModels if not m.name().startswith("FG")) # long time
True

pars()¶

Method to get the parameters of the ambient space (namely \(t\)).

This method returns all the parameters that we can find in the coefficients field of the WalkModel. See method base_ring() for further information.

EXAMPLE:

sage: from comb_walks.walkmodel import WalkModel; m = WalkModel.example_model() sage: m.pars() t

All the models in the list have only one parameter:

sage: from comb_walks.walkmodel import AllModels
sage: all(m.pars() == other.pars() for other in AllModels)
True

plot()¶

Method to plot the valid steps for a model.

This method creates a plot Sage image that displays with blue arrows the valid steps of this model. It is important to remark that currently this depiction of the model does not include the weights of the given steps.

plot_walk(size, start=(0, 0), restriction='quarter', **kwds)¶

This method depicts a random walk valid for this model.

This method creates a random walk valid for the model (see method random_walk()). The picture prints with arrows all the middle steps and make a transition in colors from the beginning of the walk until the end.

INPUT::

size: number of steps of the random walk.
start: starting point for the generated random walk.
restriction: restriction for the random walk (see random_walk())
kwds: this method allows extra parameters:
- init_color: a valid input for rgbcolor. This will be the color from the beginning of the walk. This value is set to "blue" by default.
- end_color: a valid input for rgbcolor. This will be the color from the beginning of the walk. This value is set to "red" by default.

poles(func, model='A')¶

Method for computing poles of a rational function on the curve.

This method takes a rational function over the elliptic curve defined in the model and computes its poles. This method transform the problem to the double projective model (see method model() for further information).

In this model, we compute the zeros of the denominator of the rational function and, since these denominators are bihomogeneous polynomials, we can use methods like zeros_bihom() to compute the roots of it and then compute the points of the curve that annihilates that denominator.

Then we can use the method asymptotics() to check whether these candidates are indeed poles or not.

WARNING:

The result is given either on the double projective model (model P) or the Weierstrass model (model W).
The method catched the result internally.

INPUT:

func: rational function we want to compute poles. It has to be in the model given by the argument model.
model: the model we are working on. See method model() for further information.

OUTPUT:

A list with the poles of func on the curve. These points are given by projective coordinates either in the \((x_0:x1,y_0:y_1)\) model (for models A and P) or in the \((u:v:w)\) model (for model W).

TODO:

Add examples and tests to this doc.

static random_model(max_value=100, frac_value=True, max_steps=8)¶

Method to get a random probabilistic model

This method generates a list of probabilities for taking each of the steps using the method randint() up to the value given as an argument.

INPUT:

max_value: the maximal proportion between probabilities. Must be an integer (by default 100).
frac_value: boolean argument (True by default) that decides wheher store the weights of the steps as probabilities (i.e., elements between 0 and 1) or as integers.
max_steps: maximal number of different steps allowed in the model. This guarantees that this numbers of steps will be considered although if the random generator creates a zero weight, then this step will not be included. This value is by default \(8\).

EXAMPLE:

sage: from comb_walks import *
sage: WalkModel.random_model()
Walk Model with steps: ...)
sage: WalkModel.random_model(max_steps=4).nsteps() <= 4
True

random_step()¶

Method to get a valid step from the model.

This method computes a random step contained in the step set of the model. The probability distribution is proportional to the weight of the steps, i.e., if a step \(s_1\) has weight \(1\) and another step \(s_2\) has weight \(2\), then \(s_2\) has double probability of being chosen.

EXAMPLES:

sage: from comb_walks.walkmodel import *
sage: m = WalkModel(N,S,E)
sage: all(m.random_step() in (N,S,E) for i in range(10))
True
sage: m = WalkModel([0,1], [0,2])
sage: all(m.random_step() in ((0,1),(0,2)) for i in range(10))
True

random_walk(size, start=(0, 0), steps=False, restriction='quarter')¶

Method to create a random walk valid for the model.

This method allows the user to create a random walk using the steps from the model and where the probability distribution of the steps is propostional to their weights.

Further restrictions can be applied like:

The starting point: see argument start.
The space where the walk con go trhough: see argument restriction.

INPUT:

size: the length of the walk that will be generated. If at some point we reach a coordinate where no further steps can be applied, then we return the shorter walk.
start: coordinates of the starting point of the walk.
steps: a boolean argument to determine if the output will include all the intermidiate steps through the walk or (if False) only returns the destiny.
restriction: restriction of the walk. There are three possible choices:
- "quarter": the walk will be in the first quadrant.
- "half": the walk will be in the upper half plane.
- anything else: the walk is free to move through the whole plane.

reduction(*args, **kwds)¶

Method that computes the decomposition of a rational function w.r.t. \(\tau\).

In the methods higher_polar_part(), residue() and orbital_polar_part() we have described several descriptions of the poles of rational functions over the elliptic curve described by kernel(). In fact, we know that, for any \(f \in \mathbb{C}(E)\):

\[f = res(f) + \sum_{P \in E} pol_P(f).\]

In fact, that sum over \(P \in E\) is finite since the number of poles of \(f\) is finite. Now we also know that these poles can be grouped in \(\tau\)-orbits (see method orbits()). Then, for any pole \(P\) of \(f\):

\[\sum_{n \in \mathbb{Z}} pol_{\tau^n(P)}(f) = opol_P(f) + \tau(h) - h,\]

for some particular \(h \in \mathbb{C}(E)\). This infinite sum is not infinite since it only applies for those \(n\) that \(\tau^n(P)\) was a pole of \(f\). Let \(P_0,...,P_r\) be a minimal set of poles of \(f\) such that all poles can be obtainin shifting these poles by \(\tau\). Then:

\[f = res(f) + \sum_{i=0}^r opol_{P_i}(f) + \tau(H) - H.\]

In this method we compute the three pieces: \(res(f)\), the orbital polar parts of the minimal set of poles, and \(H\).

WARNING: this method caches internally the result

INPUT:

func: the rational function to study.
poles: fixed points to look the polar behavior. If given the computations of poles of func will be skipped.
jumps: tau`-orbits of the poles. If given we skip the computation of the orbits of the poles of func and the argument poles will be understood as the orbits.
model: the model of the elliptic curve we start with. See method model() for further information.

OUTPUT:

A triplet \((A,B,C)\) such that \(A\) is the residue of func, \(B\) is a tuple with the list of the minimal set of poles and the orbital polar parts and \(C = H\).

TODO:

Add tests and examples

residue(func, model='P')¶

Method to get the residue of a function.

The higher polar part of a rational function \(f\) over an elliptic curve \(E\) on a point \(P\) is defined as a rational function \(g \in \mathbb{C}(E)\) that has a unique pole at \(P\). See method higher_polar_part() for further information.

Since these polar parts have a pole localized in just one point, we can gather all them together and remove the polar behavior of \(f\) everywhere. This remaining function is called residue:

\[f = res(f) + \sum_P pol_P(f)\]

REMARK: if \(res(f)\) has no poles, then it is constant on the curve.

INPUT:

func: rational representation of the function \(f\).
model: model to interpret the function \(f\). See method model() for further information.

OUTPUT:

A tuple with the values \((res(f), \sum_P pol_P(f))\).

TODO:

Add examples and tests

ring(model)¶

Method to get the current coordinate ring of the ambient space of the curve depending on the model required.

Since there are three different models, we have three different ambient spaces:

For model A: polynomial ring in \(x\), \(y\), \(z\) over \(Q(t)\).
For model W: polynomial ring in \(u\), \(v\), \(w\) over \(Q(t)\).
For model P: polynomial ring in \(x_0\), \(x_1\), \(y_0\), \(y_1\) over \(Q(t)\).

REMARK:

This method will return a new element if we find a needed algebraic extension. Hence, the use of this method instead of a variable is highly recommended.

INPUT:

model: the type of ambient space we look. See method model() for further information.

EXAMPLES:

sage: from comb_walks.walkmodel import WalkModel; m = WalkModel.example_model()
sage: x,y,z = m.vars(1); u,v,w = m.vars(2); x0,x1,y0,y1 = m.vars(3); t = m.pars()
sage: all(m.ring(el) == m.base_ring()[x,y,z] for el in [1,'xyz','xy','a','A'])
True
sage: all(m.ring(el) == m.base_ring()[u,v,w] for el in [2, 'uvw', 'uv', 'w', 'weierstrass', 'W'])
True
sage: all(m.ring(el) == m.base_ring()[x0,x1,y0,y1] for el in [3, 'x0x1y0y1', 'x0y0', 'p', 'projective', 'P'])
True

These relation between the base_ring() and the coordinate rings has to be preserved even after changing the base ring (see method change_ring()):

sage: nF = FractionField(NumberField(QQ['i']('i^2+1'), 'i')[t])
sage: m.change_ring(nF)
sage: all(m.ring(el) == m.base_ring()[x,y,z] for el in [1,'xyz','xy','a','A'])
True
sage: all(m.ring(el) == m.base_ring()[u,v,w] for el in [2, 'uvw', 'uv', 'w', 'weierstrass', 'W'])
True
sage: all(m.ring(el) == m.base_ring()[x0,x1,y0,y1] for el in [3, 'x0x1y0y1', 'x0y0', 'p', 'projective', 'P'])
True

solve_finite_order_tau(order)¶

Method to get the values of the parameter to get finite order on \(\tau\).

The method \(\tau\) defined over the algebraic curve of the model have sometimes a finite order and, in other ocasions, infinite order. However, these computations are generic, i.e., we compute the order of \(\tau\) independently of the value of the parameter \(t\). It could happen that there are some values of the parameter \(t\) that changes the order of \(\tau\) (namely, it may be smaller).

This method computes, fixed a defined order, the values of \(t\) that makes the map \(\tau\) have the corresponding order.

INPUT:

order: positive integer to set the order we are looking into.

OUTPUT:

The output of this method is the result of the Sage method solve over a list of expressions.

EXAMPLE:

sage: from comb_walks import *
sage: m = EllipticC[0]; m
Walk Model (wIA.01)
sage: m.solve_finite_order_tau(1)
[]
sage: m.solve_finite_order_tau(2)
[]
sage: m.solve_finite_order_tau(3)
[[t == 0]]
sage: m.solve_finite_order_tau(4)
[[t == 1/4*I*sqrt(3) - 1/4], 
 [t == -1/4*I*sqrt(3) - 1/4], 
 [t == 1/4*I*sqrt(3) + 1/4], 
 [t == -1/4*I*sqrt(3) + 1/4]]         

If the values of \(t\) are generic (i.e., the generic group is finite) this method returns [“all”] in the appropriate orders:

sage: m = FiniteGroup[0]; m
Walk Model (FG-BMM-1.01)
sage: m.solve_finite_order_tau(2)
['all']
sage: m.solve_finite_order_tau(3)
[]

For non-elliptic models (i.e., singular models) we do not perform any computation and a NonEllipticError is raised:

sage: m = NonEllipticC[0]; m
Walk Model (NE-DHRS-1)
sage: m.solve_finite_order_tau(2)
Traceback (most recent call last):
...
NonEllipticError: the model Walk Model (NE-DHRS-1) is not elliptic

step()¶

Method that return the step Laurent polynomial associated with the Model.

Given a model for walks, the step rational function is determined by the valid steps of the model. Let \((P_0,\ldots,P_n)\) be a valid walk. This walk makes a contribution on the generating function depending on what is its destiny and what which steps it makes.

In fact, each step \((s_x, s_y)\) with weight \(w\) make a contribution of \(wx^{s_x}y^{s_y}t\). In this way, we define the step rational function as the sum of all the possible contributions of the valid steps of the model.

This rational function is always a Laurent polynomial, i.e., a rational function that can be polynomialy expressed in \(x\), \(y\), \(1/x\) and \(1/y\).

EXAMPLES:

sage: from comb_walks.walkmodel import *
sage: m = WalkModel(N,E,S,W); m.step()
(x^2*y + x*y^2 + x + y)/(x*y)
sage: m.step() == (y + x + 1/y + 1/x)
True

steps()¶

Method that return the step set for this Walk Model

This method returns a list with pairs \((s, w_s)\) where \(s\) is a valid step for the model and \(w_s\) is the corresponding weight associated to \(s\).

EXAMPLES:

sage: from comb_walks.walkmodel import *
sage: m = WalkModel(N,S, [1,1,3]); m.steps()
[((0, 1), 1), ((0, -1), 1), ((1, 1), 3)]
sage: m = WalkModel(NW,S, [2,3,1], [2,5,5]); m.steps()
[((-1, 1), 1), ((0, -1), 1), ((2, 3), 1), ((2, 5), 5)]

tau(model='A')¶

Method to compute the map \(\tau\) over the kernel curve.

This map computes the map \(\tau\) and simplifies the result.

INPUT:

model: model of the elliptic curve we work on. See method model() for further information.

OUTPUT:

The map \(\tau\) in the representation requested by the argument model.

EXAMPLES:

sage: from comb_walks import * 
sage: WalkModel.example_model().tau('p')
Scheme endomorphism of Closed subscheme of Product of projective spaces P^1 x P^1 ...
(-t)*x0*x1*y0^2 + (-t)*x0^2*y0*y1 + x0*x1*y0*y1 + (-t)*x1^2*y0*y1 + (-t)*x0*x1*y1^2
Defn: Defined by sending (x0 : x1 , y0 : y1) to 
        (-x1 : -x0 , -y1 : -y0).
sage: WalkModel.example_model().tau('a')
Scheme endomorphism of Closed subscheme of Projective Space of dimension 2 ...
(-t)*x^2*y + (-t)*x*y^2 + x*y*z + (-t)*x*z^2 + (-t)*y*z^2
Defn: Defined on coordinates by sending (x : y : z) to
        (-y*z : -x*z : -x*y)

If a model is not elliptic (see method is_elliptic()), the method raise a NonEllipticError when asking for Weierstrass representation:

sage: NonEllipticC[0].tau('p')
Scheme endomorphism of Closed subscheme of Product of projective spaces P^1 x P^1 ...
(-t)*x0*x1*y0^2 + (-t)*x1^2*y0^2 + x0*x1*y0*y1 + (-t)*x0^2*y1^2
Defn: Defined by sending (x0 : x1 , y0 : y1) to 
        (-x0^3*y1^2 : -x0^2*x1*y0^2 + (-2)*x0*x1^2*y0^2 - x1^3*y0^2 , -x0^2*y1 : -x0*x1*y0 - x1^2*y0).
sage: NonEllipticC[0].tau('w')
Traceback (most recent call last):
...
NonEllipticError: The kernel is not a elliptic curve --> No Weierstrass model

telescoping(*args, **kwds)¶

Method to compute a telescoper (of possible) of a rational function over the kernel curve.

This method takes a function \(f \in \mathbb{C}(E)\) and computes a telescoper equation of the shape

\[L \cdot f = \tau(g) - g\]

where \(\tau\) is the isomorphism described in tau(), \(g\) is a rational function over the elliptic curve described by the kernel equation (see method curve()) and \(L\) is a linear differential operator on the derivation \(\delta\) defined on the method derivative().

In case that is not possible, the method will raise an error with the reason.

INPUT:

func: rational function to telescope.
model: model of the elliptic curve we work on. See method model() for further information.

OUTPUT:

A tuple with \((L,g)\) where \(L\) is a list of coefficients for the linear operator and \(g\) is the rational certificate for the telescoper.

TODO:

Add test and examples.

vars(model)¶

Method to retrieve the current variables employed in one particular model of the curve.

Remark: this method will return a new element if we find a needed algebraic extension. Hence, the use of this method instead of a variable is highly recommended.

INPUT:

model: the type of ambient space we look. See method model() for further information.

EXAMPLES:

sage: from comb_walks.walkmodel import WalkModel; m = WalkModel.example_model()
sage: all(str(m.vars(el)) == "(x, y, z)" for el in [1,'xyz','xy','a','A'])
True
sage: all(str(m.vars(el)) == "(u, v, w)" for el in [2, 'uvw', 'uv', 'w', 'weierstrass', 'W'])
True
sage: all(str(m.vars(el)) == "(x0, x1, y0, y1)" for el in [3, 'x0x1y0y1', 'x0y0', 'p', 'projective', 'P'])
True

weight(step)¶

Method to get the weight associated with a particular step

This method is a getter from the variable steps() which extracts the weight information of a particular step. If such step is not in the model, this method returns 0.

INPUT:

step: a step in a tuple format. This tuple will be casted into a tuple of Integer, in order to use the equality of tuples to check whether the step is in the model or not.

OUTPUT:

The value of the weight of the step in the walk. If the step is not present, then the returned value is zero.

EXAMPLES:

sage: from comb_walks import *
sage: m = RookModel
sage: all(m.weight(el) == 1 for el in [N,S,E,W])
True
sage: all(m.weight(el) == 0 for el in [NE, NW, SW, SE])
True
sage: m.weight((0,0))
0
sage: m = WalkModel(N,S,E,W,(0,0,Integer(1)/2))
sage: all(m.weight(el) == 1 for el in [N,S,E,W])
True
sage: all(m.weight(el) == 0 for el in [NE, NW, SW, SE])
True
sage: m.weight((0,0))
1/2

weight_matrix()¶

Method to get the probability matrix for this model.

This method (only working right now for models with small steps) follows the definitions on the book by Fayolle et al. This books propose to study a matrix generated by the probabilities of jumping to the new position.

Since this probability is marked by the weights of the steps, we construct an equivalent matrix using these weights:

\[\begin{split}\left(\begin{array}{ccc} w_{-1,1} & w_{0,1} & w_{1,1}\\ w_{-1,0} & w_{0,0}-S & w_{1,0}\\ w_{-1,-1} & w_{0,-1} & w_{1,-1} \end{array}\right)\end{split}\]

where \(S\) is the sum of all weights.

EXAMPLES:

sage: from comb_walks import *
sage: m = RookModel; m.weight_matrix()
[ 0  1  0]
[ 1 -4  1]
[ 0  1  0]
sage: m = KingModel; m.weight_matrix()
[ 1  1  1]
[ 1 -8  1]
[ 1  1  1]
sage: m = WalkModel((2,1,1), N, S, E); m.weight_matrix()
Traceback (most recent call last):
...
TypeError: The model is not of short steps
sage: m = WalkModel(N,S,E,W,(0,0,Integer(1)/2)); m.weight_matrix()
[ 0  1  0]
[ 1 -4  1]
[ 0  1  0]

Using Lemma 4.1.1 from Fayolle’s book, we have that the order of \(\tau\) is \(2\) if and only if the determinant of this matrix is exactly zero:

sage: all(ModelDict["FG-BMM-1.%02d" %i].weight_matrix().determinant() == 0 for i in range(1,11))
True

weight_minor_matrix()¶

Method to get the matrix of minors of the weight matrix

This method comptues the matrix composed by minors from the weight matrix (see method weight_matrix()) in such an order that fits equation (4.1.6) from Fayolle’s book.

\[\begin{split}\begin{pmatrix} \Delta_{2,3} & \Delta_{3,3} & \Delta_{2,2} & \Delta_{3,2}\\ \Delta_{1,3} & -\Delta_{2,3} & \Delta_{1,2} & -\Delta_{2,2}\\ \Delta_{2,2} & \Delta_{3,2} & \Delta_{2,1} & \Delta_{3,1}\\ \Delta_{1,2} & -\Delta_{2,2} & \Delta_{1,1} & -\Delta_{2,1} \end{pmatrix},\end{split}\]

where \(\Delta_{i,j}\) is the 2-minor from the weight matrix after removing the `i`th row and the `j`th column.

EXAMPLE:

sage: from comb_walks import *
sage: m = ModelDict["FG-BMM-1.02"]
sage: m.weight_minor_matrix()
[ 0 -4  0  0]
[ 4  0  0  0]
[ 0  0  0  4]
[ 0  0 -4  0]
sage: m.weight_minor_matrix().determinant()
256

The determinant of this matrix indicates if the map \(\tau\) has order 3:

sage: sage: all(ModelDict["FG-BMM-2.%d" %i].weight_minor_matrix().determinant() == 0 for i in range(1,6))

Models of Walks in the Quarter Plane¶

Previous topic

This Page