Demo: SageMath's Asymptotic Expansion Module

Demo - ACSV.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e331f64b-10d1-4d8f-a628-f11cdf13e7a1",
   "metadata": {
    "tags": []
   },
   "source": [
    "## `sage_acsv`: Rigorous Analytic Combinatorics in Several Variables in SageMath\n",
    "##### Benjamin Hackl, Andrew Luo, Steve Melczer, Jesse Selover, Elaine Wong"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "024a0fef-67d7-447d-8cc6-b34bf125cadb",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from sage_acsv import diagonal_asy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "223b1ce4-aecd-4665-8916-265c25a473e2",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%display typeset"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "54a927da-f284-4631-a637-7592cd69540c",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Example 1: (Central) Binomial Coefficients\n",
    "\n",
    "Simple toy example: Binomial coefficients! They are generated by\n",
    "$$ \\frac{1}{1 - x - y} = \\sum_{n\\geq 0} (x + y)^n = \\sum_{a, b \\geq 0} \\binom{a + b}{a} x^a y^b. $$\n",
    "\n",
    "Diagonal in direction $\\mathbf{r} = (r_1, r_2)$ gives\n",
    "$$ [x^{nr_1} y^{nr_2}] \\frac{1}{1 - x - y} = \\binom{n(r_1 + r_2)}{nr_1}. $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a3a0c11a-b51f-4719-87c4-a4351619793c",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "var('x y')\n",
    "central_binomial_asy = diagonal_asy(1/(1 - x - y), r=(1, 1), output_format=\"asymptotic\")\n",
    "central_binomial_asy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "da0812f1-fa55-47ea-8673-eec255dded1a",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "\n",
    "diagonal_asy(1/(1 - x - y), r=(37, 5), output_format=\"asymptotic\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8c967f63-0169-456c-bff0-28cbf94bc63a",
   "metadata": {},
   "source": [
    "### Example 2: A sequence related to $\\zeta(3)$ / Apéry\n",
    "\n",
    "The sequence\n",
    "$$ f_n = \\sum_{k=1}^n \\binom{n}{k}^2 \\binom{n+k}{k}^2 $$\n",
    "was used by Apéry in his proof of the irrationality of $\\zeta(3)$. It can be written as the $(1, 1, 1, 1)$-diagonal of\n",
    "$$ F(w, x, y, z) = \\frac{1}{1 - w(1+x)(1+y)(1+z)(xyz + yz + y + z + 1)}. $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "98b156ba-8e70-4ff4-9a7a-9150f1704fc4",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "var(\"w x y z\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c327962c-5365-4680-911e-64af243f43a5",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "apery_asy = diagonal_asy(\n",
    "    1/(1 - w*(1+x)*(1+y)*(1+z)*(x*y*z + y*z + y + z + 1)),\n",
    "    output_format=\"asymptotic\",\n",
    ")\n",
    "apery_asy"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c4f10d0e-8a49-48ef-b242-6efa5e2eeaff",
   "metadata": {},
   "source": [
    "The (current) default output format is a list of tuples $(\\rho, n^s, \\pi^s, C)$ corresponding to an asymptotic contribution of $C \\pi^s \\cdot \\rho^n n^s$. This can be used to do some post-processing:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c4a03ff2-b176-486c-b5d9-9e4fb20a427b",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "apery_asy_tuples = diagonal_asy(\n",
    "    1/(1 - w*(1+x)*(1+y)*(1+z)*(x*y*z + y*z + y + z + 1)),\n",
    ")\n",
    "apery_asy_tuples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f0a93a90-f44a-453c-afd9-b3e7bb03d9ee",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "var(\"n\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0511e501-ec5d-4597-8860-6cdc0491bf77",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "(rho, n_s, pi_s, C) = apery_asy_tuples[0]\n",
    "C * pi_s * rho^n * n_s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "29e3c0cd-271f-4931-b38e-6ce490b79d74",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "rho.parent(), C.parent()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a61a05d1-006b-45ce-bb28-3319dfaa6002",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "rho.degree(), C.degree()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "70eda1ea-afd6-48bd-8ef6-9e58bee64fef",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "C.minpoly()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6b49facb-0c76-4465-bdb6-3708850edfca",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "C.radical_expression() * pi_s * (rho.radical_expression())^n * n_s"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "33407b9d-1232-4ffc-8416-7b7914b7e10d",
   "metadata": {},
   "source": [
    "### Example 3: Delannoy numbers\n",
    "\n",
    "The Delannoy number $D(m, n)$ counts the number of lattice paths in an $(m\\times n)$-grid from $(0, 0)$ to $(m, n)$ using steps $(1, 0)$, $(0, 1)$, $(1, 1)$.\n",
    "\n",
    "![Delannoy Walks](https://upload.wikimedia.org/wikipedia/commons/thumb/e/e7/Delannoy3x3.svg/600px-Delannoy3x3.svg.png)\n",
    "\n",
    "Their generating function is rational with\n",
    "$$ D(m, n) = [x^m y^n] \\frac{1}{1 - x - y - xy}. $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "08646d5f-2e94-4044-b18f-a3c058c30813",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "delannoy_asy = diagonal_asy(\n",
    "    1/(1 - x - y - x*y),\n",
    "    r=(1, 1),\n",
    "    output_format=\"asymptotic\"\n",
    ")\n",
    "delannoy_asy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0363c624-8ebb-4137-b10e-75523a0fba55",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "delannoy_asy_tuple = diagonal_asy(\n",
    "    1/(1 - x - y - x*y),\n",
    "    r=(1, 1),\n",
    "    output_format=\"tuple\"\n",
    ")\n",
    "rho, pi_s, n_s, C = delannoy_asy_tuple[0]\n",
    "C.radical_expression() * pi_s * rho.radical_expression()^n * n_s"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dfb9b438-75a1-4288-9f8d-8a34627c55cd",
   "metadata": {},
   "source": [
    "### Example 4: We can detect whether there are no minimal (smooth, simple) critical points."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ee6c7ed6-b003-4ed0-8651-4ec7b5b3e959",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "diagonal_asy(  # raises an ASCVException\n",
    "    1/(x^4*y + x^3*y + x^2*y + x*y - 1)\n",
    ")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 10.0",
   "language": "sage",
   "name": "sagemath-10.0"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}

Demo - Asymptotic Expansions.ipynb

Dockerfile

FROM sagemath/sagemath:10.5

ARG NB_UID=1000
ARG NB_USER=sage

USER root
RUN apt update && apt install -y python3 python3-pip

USER ${NB_UID}
ENV PATH="${PATH}:${HOME}/.local/bin"
RUN pip3 install notebook
RUN sage -pip install sage_acsv
RUN ln -s $(sage -sh -c 'ls -d $SAGE_VENV/share/jupyter/kernels/sagemath') $HOME/.local/share/jupyter/kernels/sagemath-dev

# partially superfluous -- create separate directory to hold notebooks
WORKDIR ${HOME}/notebooks
COPY --chown=${NB_UID}:${NB_UID} . .
USER root
RUN chown -R ${NB_UID}:${NB_UID} .
USER ${NB_UID}

ENTRYPOINT []