Toolbox for Asymptotics with Explicit Error Bounds¶

In [1]:

import dependent_bterms as dbt

In [2]:

%display typeset

Creating a special `AsymptoticRing`¶

See the documentation of SageMath's module on asymptotic expansions for a primer on the AsymptoticRing.

Assume that we want to carry out computations in a setting where we have a variable $n\to\infty$, as well as a dependent variable $k = k(n)$ for which we know $n^{\alpha} \leq k \leq n^{\beta}$ for some $0\leq\alpha\leq\beta$. Concretely, let us consider $1 = n^0 \leq k\leq n^{4/7}$.

Note: This implementation currently only supports monomial asymptotic growth of the independent variable. Trying to use it with more intricate growth groups other than $n^{\mathbb{Q}}$ will likely result in unwanted behavior.

In [3]:

AR, n, k = dbt.AsymptoticRingWithDependentVariable(
    "n^QQ", "k", 0, 4 / 7, bterm_round_to=3, default_prec=5
)

Technically, k is a plain symbolic variable -- the instantiated Asymptotic Ring uses the Symbolic Ring as its coefficient ring:

In [4]:

AR

Out[4]:

In [5]:

k in SR

Out[5]:

$\displaystyle \mathrm{True}$

Arithmetic with the dependent variable¶

Arithmetic with the expansions from our special Asymptotic Rign works as usual:

In [6]:

(1 + 3 * n) * (4 * n ^ (-7 / 3) + 42 / n + 1)

Out[6]:

$\displaystyle 3 n + 127 + 42 n^{-1} + 12 n^{-\frac{4}{3}} + 4 n^{-\frac{7}{3}}$

In [7]:

prod((1 + n ^ (-j)) for j in srange(1, 10)) * (1 + O(n ^ (-10)))

Out[7]:

$\displaystyle 1 + n^{-1} + n^{-2} + 2 n^{-3} + 2 n^{-4} + 3 n^{-5} + 4 n^{-6} + 5 n^{-7} + 6 n^{-8} + 8 n^{-9} + O\!\left(n^{-10}\right)$

In [8]:

n / (n - 1)

Out[8]:

$\displaystyle 1 + n^{-1} + n^{-2} + n^{-3} + n^{-4} + O\!\left(n^{-5}\right)$

We can also simply use the dependent variable.

In [9]:

expr = k * n ^ 2 + O(n ^ (3 / 2)) + k ^ 3 * n
expr

Out[9]:

$\displaystyle k^{3} n + k n^{2} + O\!\left(n^{\frac{3}{2}}\right)$

Notice that the term order is now constructed with respect to the highest potential growth of a summand (i.e., if $k = k(n)$ were to assume its upper bound). We can ask the summands to reveal their respective growth bounds; the following tuples describe the lower and the upper bound of a summand, respectively:

In [10]:

for summand in expr.summands.elements_topological():
    print(f"{summand} -> {summand.dependent_growth_range()}")

O(n^(3/2)) -> (n^(3/2), n^(3/2))
k*n^2 -> (n^2, n^(18/7))
k^3*n -> (n, n^(19/7))

Automatic expansions work too:

In [11]:

auto_expansion = exp((1 + k) / n)
auto_expansion

Out[11]:

$\displaystyle 1 + \left(k + 1\right) n^{-1} + \left(\frac{1}{2} \, {\left(k + 1\right)}^{2}\right) n^{-2} + \left(\frac{1}{6} \, {\left(k + 1\right)}^{3}\right) n^{-3} + \left(\frac{1}{24} \, {\left(k + 1\right)}^{4}\right) n^{-4} + O\!\left(n^{-\frac{15}{7}}\right)$

Note that the error term, $O(n^{-15/7})$, would be able to absorb some parts of the exact terms, after expanding the powers of $(k+1)$. This is not done automatically, but can easily be triggered via a utility function from our toolbox:

In [12]:

dbt.simplify_expansion(auto_expansion)

Out[12]:

$\displaystyle 1 + \left(k + 1\right) n^{-1} + \left(\frac{1}{2} \, k^{2} + k + \frac{1}{2}\right) n^{-2} + \left(\frac{1}{6} \, k^{3} + \frac{1}{2} \, k^{2}\right) n^{-3} + \frac{1}{24} \, k^{4} n^{-4} + O\!\left(n^{-\frac{15}{7}}\right)$

Now only the certified lower-order terms remain.

Expansions with explicit error bounds: B-terms¶

B-terms are, in a nutshell, O-terms with explicitly specified bound constant and validity point. The term $$ B_{n\geq 10}(42 n^{3}) $$ represents an error term, valid from $n \geq 10$, that is bounded by $42 n^3$. Basic support for arithmetic (over univariate, monomial growth groups) is shipped with a standard installation of SageMath. Our specialized asymptotic ring extends this functionality to expansions involving the dependent variable $k = k(n)$.

In [13]:

7 * n + AR.B(5 / n, valid_from=10) + 3 / n ^ 2

dependent_bterms/structures.py:362: FutureWarning: This class/method/function is marked as experimental. It, its functionality or its interface might change without a formal deprecation.
See https://github.com/sagemath/sage/issues/31922 for details.
  super().__init__(

Out[13]:

$\displaystyle 7 n + B_{n \ge 10}\left(\frac{53}{10} n^{-1}\right)$

The constant $53/10$ is obtained from automatically estimating $$ \frac{3}{n^2} = \frac{3}{n\cdot n} \leq \frac{3}{10 n}, $$ and then letting the existing B-term absorb this bound.

To avoid the accumulation of complicated symbolic expressions appearing when carrying out this automatic estimate, we have specified (via bterm_round_to) above that B-term constants should be rounded:

In [14]:

AR.B(1 / n, valid_from=10) + n ^ (-4 / 3)

Out[14]:

$\displaystyle B_{n \ge 10}\left(\frac{293}{200} n^{-1}\right)$

where the constant is $\big\lceil (1 + \frac{1}{10^{1/3}}) \cdot 10^3\big\rceil \cdot 10^{-3} = \frac{293}{200}$. This mechanism significantly improves performance for large expansions.

For B-terms to work with the dependent variable, some special absorption rules are in place:

In [15]:

AR.B(3 * k ^ 2 / n ^ 3, valid_from=10) + (1 - 2 * k + 3 * k ^ 2 - 4 * k ^ 3) / n ^ 5

Out[15]:

$\displaystyle B_{n \ge 10}\left(\frac{3373}{1000} \, {\left| k^{2} \right|} n^{-3}\right)$

We first estimate $$ \bigg\lvert\frac{1 - 2k + 3k - 4k^3}{n^5}\bigg\rvert \leq \frac{(1 + 2 + 3 + 4) k ^3}{n^5} = \frac{10 k^3}{n^5}. $$ As the power of $k$ in this bound is larger than the maximal power of $k$ in the B-term, we may not yet proceed as above (otherwise we would increase the upper bound of the B-term, which we must avoid). Instead, we use first use $k\leq n^{4/7}$, followed by $n\geq 10$ to obtain $$ \frac{10 k^3}{n^5} \leq \frac{10 k^2 n^{4/7}}{n^5} = \frac{10 k^2}{n^{31/7}} \leq \frac{10 k^2}{10^{10/7} \cdot n^3} = 10^{-3/7} \cdot \frac{k^2}{n^3}, $$ which the B-term now can absorb directly. Hence the value of the B-term constant is determined via $\lceil (3 + 10^{-3/7}) \cdot 10^3 \rceil \cdot 10^{-3} = \frac{3373}{1000}$.

This module also ships with support for B-term bounded Taylor expansions. From a technical point of view, the error term (in its Lagrange form) is determined rigorously using interval arithmetic.

In [16]:

arg = (1 + k) / n + AR.B(k ^ 3 / n ^ 3, valid_from=10)
ex = dbt.taylor_with_explicit_error(
    lambda t: 1 / (1 - t ^ 2), arg, order=3, valid_from=10
)
ex

Out[16]:

$\displaystyle 1 + \left({\left(k + 1\right)}^{2}\right) n^{-2} + B_{n \ge 10}\left(\left({\left| \frac{7351}{250} \, k^{3} + 30 \, k^{2} + 30 \, k + 10 \right|}\right) n^{-3}\right)$

Simplification (involving partial absorption of coefficients) may lead to situations where terms of technically weaker growth cannot (as a limitation of the current implementation) be absorbed by the constructed error term. In this case the returned expansion is still correct; just not as compact as it could be.

In [17]:

dbt.simplify_expansion(ex)

Out[17]:

$\displaystyle 1 + k^{2} n^{-2} + B_{n \ge 10}\left(\left({\left| \frac{7351}{250} \, k^{3} + 30 \, k^{2} + 30 \, k + 10 \right|}\right) n^{-3}\right) + \left(2 \, k + 1\right) n^{-2}$

By specifying simplify_bterm_growth=True, simplifying an expansion also collapses the dependent variables in all B-terms, resulting in an expansion involving a single, "absolute" B-term.

In [18]:

dbt.simplify_expansion(ex, simplify_bterm_growth=True)

Out[18]:

$\displaystyle 1 + k^{2} n^{-2} + B_{n \ge 10}\left(\frac{41441}{1000} n^{-\frac{9}{7}}\right)$

In [ ]:

Toolbox for Asymptotics with Explicit Error Bounds¶

Creating a special AsymptoticRing¶

Arithmetic with the dependent variable¶

Expansions with explicit error bounds: B-terms¶

Creating a special `AsymptoticRing`¶