Benjamin Hackl

Asymptotic Expressions: Current Developments

Since my last blog entry on the status of our implementation of Asymptotic Expressions in SageMath quite a lot of improvements have happened. Essentially, all the pieces required in order to have a basic working implementation of multivariate asymptotics are there. The remaining tasks within my Google Summer of Code project are:

• Polish the documentation of our minimal prototype, which consists of #17716 and the respective dependencies. Afterwards, we will set this to needs_review.

• Open a ticket for the multivariate asymptotic ring and put together everything that we have written so far there.

In this blog post I want to give some more examples of what can be done with our implementation right now and what we would like to be able to handle in the future.

Status Quo

After I wrote my last blog entry, we introduced a central idea/interface to our project: short notations. By using the short notation factory for growth groups (introduced in #18930) it becomes very simple to construct the desired growth group. Essentially, monomial growth groups (cf. #17600), i.e. groups that contain elements of the form variable^power (for a fixed variable and powers from some base ring, e.g. the Integer Ring or even the Rational Field) are represented by variable^base, where the base ring is also specified via its shortened name.

The short notation factory then enables us to do the following:

sage: from sage.groups.asymptotic_growth_group import GrowthGroup
sage: G = GrowthGroup('x^ZZ'); G
Growth Group x^ZZ
sage: G.an_element()
x
sage: G = GrowthGroup('x^QQ'); G
Growth Group x^QQ
sage: G.an_element()
x^(1/2)

Naturally, this interface carries over to the generation of asymptotic rings: instead of the (slightly dubious) "monomial" keyword advertised in my last blog entry, we can now actually construct the growth group by specifying the respective growth group via its short representation:

sage: R.<x> = AsymptoticRing('x^ZZ', QQ); R
Asymptotic Ring <x^ZZ> over Rational Field
sage: (x^2 + O(x))^50
x^100 + O(x^99)

Recently, we also implemented another type of growth group: exponential growth groups (see #19028). These groups represent elements of the form base^variable where the base is from some multiplicative group. For example, we could do the following:

sage: G = GrowthGroup('QQ^x'); G
Growth Group QQ^x
sage: G.an_element()
(1/2)^x
sage: G(2^x) * G(3^x)
6^x
sage: G(5^x) * G((1/7)^x)
(5/7)^x

Note: unfortunately, we did not implement a function that allows taking some element from some growth group (e.g. $x$ from a monomial growth group) as the variable in an exponential growth group yet. Implementing some way to “change” between growth groups by taking the log or the exponential function is one of our next steps.

We also made this short notation a central interface for working with cartesian products. This is implemented in #18587. For example, this allows to construct growth groups containing elements like $2^x \sqrt[5]{x^2} \log(x)^2$:

sage: G = GrowthGroup('QQ^x * x^QQ * log(x)^ZZ'); G
Growth Group QQ^x * x^QQ * log(x)^ZZ
sage: G.an_element()
(1/2)^x * x^(1/2) * log(x)
sage: G(2^x * x^(2/5) * log(x)^2)
2^x * x^(2/5) * log(x)^2

Simple parsing from the symbolic ring (and from strings) is implemented. Like I have written above, operations like 2^G(x) or log(G(x)) are one of the next steps on our roadmap.

Further Steps

Of course, having an easy way to generate growth groups (and thus also asymptotic rings) is nice — however, it would be even better if the process of finding the correct parent would be even more automated. Unfortunately, this requires some non-trivial effort regarding the pushout construction — which will certainly not happen within the GSoC project.

As soon as we have an efficient way to “switch” between factors of a growth group (e.g. by taking the logarithm or the exponential function), this has to be carried over up to the asymptotic ring. Operations like

sage: 2^(x^2 + O(x))
2^(x^2) * 2^(O(x))

where the output could also be 2^(x^2) * O(x^g), where g is determined by series_precision().

Division of asymptotic expressions can be realized with just about the same idea, for example:

and so on. If an infinite series occurs, it will have to be cut using an O-Term, most likely somehow depending on series_precision() as well.

Ultimately, we would also like to incorporate, for example, Stirling’s approximation of the factorial such that we could do something like

sage: n.factorial()
sqrt(2*pi) * e^(n*log(n)) * (1/e)^n * n^(1/2) + ...

which then can be used to obtain asymptotic expansions of binomial coefficients like $\binom{2n}{n}$:

sage: (2*n).factorial() / (n.factorial()^2)
1/sqrt(pi) * 4^n * n^(-1/2) + ...

As you can see, there is still a lot of work within our “Asymptotic Expressions” project — nevertheless, with the minimal working prototype and the ability to create cartesian products of growth groups, the fundament for all of this is already implemented! 😉