{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "### This notebook contains worked examples from Chapter 4 of the text *Analytic Combinatorics in Several Variables (2nd edition)* by Pemantle, Wilson and Melczer. \n", "\n", "Further details can be found on the book website at [https://acsvproject.com/acsvbook/](https://acsvproject.com/acsvbook/) .\n", "\n", "Example numbers match the published version.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Lemma 4.5 - Compositional Inverse" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "# Compute compositional inverse using a Newton iteration (which is computationally faster)\n", "# Function takes a function F as a series to order O(x^M)\n", "def Newton(F,M):\n", " y = x/F.diff(x).subs(x=0)\n", " K = RR(log(M,2)).floor()\n", " for k in range(1,K+1):\n", " y = (y - y.diff(x) * (F.subs(x=y)-x)).series(x,2^(k+1)).truncate().polynomial(QQ)\n", " return SR(y).series(x,M).truncate().polynomial(QQ)" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\verb|The|\\verb| |\\verb|inverse|\\verb| |\\verb|of|\\verb| |\\verb|\t| \\sin\\left(x\\right) \\verb| |\\verb|=|\\verb| |\\verb|\t| -\\frac{1}{121645100408832000} x^{19} + \\frac{1}{355687428096000} x^{17} - \\frac{1}{1307674368000} x^{15} + \\frac{1}{6227020800} x^{13} - \\frac{1}{39916800} x^{11} + \\frac{1}{362880} x^{9} - \\frac{1}{5040} x^{7} + \\frac{1}{120} x^{5} - \\frac{1}{6} x^{3} + x\\)" ], "text/latex": [ "$\\displaystyle \\verb|The|\\verb| |\\verb|inverse|\\verb| |\\verb|of|\\verb| |\\verb|\t| \\sin\\left(x\\right) \\verb| |\\verb|=|\\verb| |\\verb|\t| -\\frac{1}{121645100408832000} x^{19} + \\frac{1}{355687428096000} x^{17} - \\frac{1}{1307674368000} x^{15} + \\frac{1}{6227020800} x^{13} - \\frac{1}{39916800} x^{11} + \\frac{1}{362880} x^{9} - \\frac{1}{5040} x^{7} + \\frac{1}{120} x^{5} - \\frac{1}{6} x^{3} + x$" ], "text/plain": [ "'The inverse of \\t' \\sin\\left(x\\right) ' = \\t' -1/121645100408832000*x^19 + 1/355687428096000*x^17 - 1/1307674368000*x^15 + 1/6227020800*x^13 - 1/39916800*x^11 + 1/362880*x^9 - 1/5040*x^7 + 1/120*x^5 - 1/6*x^3 + x" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\verb|is|\\verb| |\\verb|the|\\verb| |\\verb|function|\\verb| |\\verb|whose|\\verb| |\\verb|series|\\verb| |\\verb|begins|\\)" ], "text/latex": [ "$\\displaystyle \\verb|is|\\verb| |\\verb|the|\\verb| |\\verb|function|\\verb| |\\verb|whose|\\verb| |\\verb|series|\\verb| |\\verb|begins|$" ], "text/plain": [ "'is the function whose series begins'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\frac{12155}{1245184} x^{19} + \\frac{6435}{557056} x^{17} + \\frac{143}{10240} x^{15} + \\frac{231}{13312} x^{13} + \\frac{63}{2816} x^{11} + \\frac{35}{1152} x^{9} + \\frac{5}{112} x^{7} + \\frac{3}{40} x^{5} + \\frac{1}{6} x^{3} + x\\)" ], "text/latex": [ "$\\displaystyle \\frac{12155}{1245184} x^{19} + \\frac{6435}{557056} x^{17} + \\frac{143}{10240} x^{15} + \\frac{231}{13312} x^{13} + \\frac{63}{2816} x^{11} + \\frac{35}{1152} x^{9} + \\frac{5}{112} x^{7} + \\frac{3}{40} x^{5} + \\frac{1}{6} x^{3} + x$" ], "text/plain": [ "12155/1245184*x^19 + 6435/557056*x^17 + 143/10240*x^15 + 231/13312*x^13 + 63/2816*x^11 + 35/1152*x^9 + 5/112*x^7 + 3/40*x^5 + 1/6*x^3 + x" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\verb|The|\\verb| |\\verb|composition|\\verb| |\\verb|of|\\verb| |\\verb|these|\\verb| |\\verb|series|\\verb| |\\verb|equals|\\)" ], "text/latex": [ "$\\displaystyle \\verb|The|\\verb| |\\verb|composition|\\verb| |\\verb|of|\\verb| |\\verb|these|\\verb| |\\verb|series|\\verb| |\\verb|equals|$" ], "text/plain": [ "'The composition of these series equals'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle 1 x + \\mathcal{O}\\left(x^{20}\\right)\\)" ], "text/latex": [ "$\\displaystyle 1 x + \\mathcal{O}\\left(x^{20}\\right)$" ], "text/plain": [ "1*x + Order(x^20)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Example inverting sin(x)\n", "F = sin(x).series(x,21).truncate().polynomial(QQ)\n", "g = Newton(F,20)\n", "show(\"The inverse of \\t\", latex(sin(x)), \" = \\t\", F)\n", "show(\"is the function whose series begins\")\n", "show(g)\n", "show(\"The composition of these series equals\")\n", "show(SR(F.subs(x=g)).series(x,20))" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\verb|The|\\verb| |\\verb|compositional|\\verb| |\\verb|inverse|\\verb| |\\verb|of|\\verb| |\\verb|a|\\verb| |\\verb|function|\\verb| |\\verb|whose|\\verb| |\\verb|series|\\verb| |\\verb|begins|\\)" ], "text/latex": [ "$\\displaystyle \\verb|The|\\verb| |\\verb|compositional|\\verb| |\\verb|inverse|\\verb| |\\verb|of|\\verb| |\\verb|a|\\verb| |\\verb|function|\\verb| |\\verb|whose|\\verb| |\\verb|series|\\verb| |\\verb|begins|$" ], "text/plain": [ "'The compositional inverse of a function whose series begins'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle d x^{4} + c x^{3} + b x^{2} + a x\\)" ], "text/latex": [ "$\\displaystyle d x^{4} + c x^{3} + b x^{2} + a x$" ], "text/plain": [ "d*x^4 + c*x^3 + b*x^2 + a*x" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\verb|is|\\verb| |\\verb|the|\\verb| |\\verb|function|\\verb| |\\verb|whose|\\verb| |\\verb|series|\\verb| |\\verb|begins|\\)" ], "text/latex": [ "$\\displaystyle \\verb|is|\\verb| |\\verb|the|\\verb| |\\verb|function|\\verb| |\\verb|whose|\\verb| |\\verb|series|\\verb| |\\verb|begins|$" ], "text/plain": [ "'is the function whose series begins'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle {(\\frac{1}{a})} x + {(-\\frac{b}{a^{3}})} x^{2} + {(\\frac{2 \\, b^{2}}{a^{5}} - \\frac{c}{a^{4}})} x^{3} + {(-\\frac{5 \\, b^{3}}{a^{7}} + \\frac{5 \\, b c}{a^{6}} - \\frac{d}{a^{5}})} x^{4} + \\mathcal{O}\\left(x^{5}\\right)\\)" ], "text/latex": [ "$\\displaystyle {(\\frac{1}{a})} x + {(-\\frac{b}{a^{3}})} x^{2} + {(\\frac{2 \\, b^{2}}{a^{5}} - \\frac{c}{a^{4}})} x^{3} + {(-\\frac{5 \\, b^{3}}{a^{7}} + \\frac{5 \\, b c}{a^{6}} - \\frac{d}{a^{5}})} x^{4} + \\mathcal{O}\\left(x^{5}\\right)$" ], "text/plain": [ "(1/a)*x + (-b/a^3)*x^2 + (2*b^2/a^5 - c/a^4)*x^3 + (-5*b^3/a^7 + 5*b*c/a^6 - d/a^5)*x^4 + Order(x^5)" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\verb|The|\\verb| |\\verb|composition|\\verb| |\\verb|of|\\verb| |\\verb|these|\\verb| |\\verb|series|\\verb| |\\verb|equals|\\)" ], "text/latex": [ "$\\displaystyle \\verb|The|\\verb| |\\verb|composition|\\verb| |\\verb|of|\\verb| |\\verb|these|\\verb| |\\verb|series|\\verb| |\\verb|equals|$" ], "text/plain": [ "'The composition of these series equals'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle x + \\mathcal{O}\\left(x^{5}\\right)\\)" ], "text/latex": [ "$\\displaystyle x + \\mathcal{O}\\left(x^{5}\\right)$" ], "text/plain": [ "x + Order(x^5)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Do Newton iteration manually over symbolic field\n", "var('a b c d x')\n", "F = a*x + b*x^2 + c*x^3 + d*x^4\n", "y = x/a\n", "y = (y - y.diff(x) * (F.subs(x=y)-x)).series(x,2^2).truncate()\n", "y = (y - y.diff(x) * (F.subs(x=y)-x)).series(x,2^3).truncate()\n", "y = y.series(x,5).expand()\n", "show(\"The compositional inverse of a function whose series begins\")\n", "show(F)\n", "show(\"is the function whose series begins\")\n", "show(y)\n", "show(\"The composition of these series equals\")\n", "show(F.subs(x=y).series(x,5).simplify_full())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 4.8\n", "\n" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\verb|[z^n]| \\frac{1}{\\sqrt{-z + 1}} \\verb| |\\verb|=|\\verb| |\\verb|\t| \\frac{1}{\\sqrt{\\pi}} n^{-\\frac{1}{2}} - \\frac{1}{8 \\, \\sqrt{\\pi}} n^{-\\frac{3}{2}} + \\frac{1}{128 \\, \\sqrt{\\pi}} n^{-\\frac{5}{2}} + O\\!\\left(n^{-\\frac{7}{2}}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\verb|[z^n]| \\frac{1}{\\sqrt{-z + 1}} \\verb| |\\verb|=|\\verb| |\\verb|\t| \\frac{1}{\\sqrt{\\pi}} n^{-\\frac{1}{2}} - \\frac{1}{8 \\, \\sqrt{\\pi}} n^{-\\frac{3}{2}} + \\frac{1}{128 \\, \\sqrt{\\pi}} n^{-\\frac{5}{2}} + O\\!\\left(n^{-\\frac{7}{2}}\\right)$" ], "text/plain": [ "'[z^n]' 1/sqrt(-z + 1) ' = \\t' 1/sqrt(pi)*n^(-1/2) - 1/8/sqrt(pi)*n^(-3/2) + 1/128/sqrt(pi)*n^(-5/2) + O(n^(-7/2))" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "SCR = SR.subring(no_variables=True) # Create symbolic ring with no variables\n", "A. = AsymptoticRing(\n", " growth_group='QQ^n * n^QQ * log(n)^QQ', \n", " coefficient_ring=SCR,\n", " default_prec=4\n", ")\n", "\n", "# Compute an asymptotic expansion\n", "def GF(z):\n", " return (1-z)^(-1/2)\n", "\n", "asm = A.coefficients_of_generating_function(\n", " function=GF,\n", " singularities=(1,),\n", " precision=3\n", ")\n", "show(\"[z^n]\", SR(\"(1-z)^(-1/2)\"), \" = \\t\", asm)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SageMath 10.1", "language": "sage", "name": "sagemath-10.1" }, "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.11.1" } }, "nbformat": 4, "nbformat_minor": 4 }