{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.24 and 2.28 (Central Binomial Coefficients Squared)\n", "Determining asymptotics of the central binomial coefficients squared. \n", "*Requirements: [ore_algebra package](https://github.com/mkauers/ore_algebra/)*" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "# Define the rings of differential and shift operators\n", "from ore_algebra import *\n", "Ind. = PolynomialRing(QQ); Shift. = OreAlgebra(Ind)\n", "Pols. = PolynomialRing(QQ); Diff. = OreAlgebra(Pols)" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "# Start with the previously calculated shift and differential operators\n", "rec = (n+1)^2*Sn - 4*(2*n+1)^2\n", "diff = z*(1-16*z)*Dz^2+(1-32*z)*Dz-4" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[16^n*n^(-1)*(1 - 1/4*n^(-1) + 1/32*n^(-2) + 1/128*n^(-3) - 5/2048*n^(-4) + O(n^(-5)))]" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Asymptotic expansions of a basis to the recurrence\n", "rec.generalized_series_solutions()" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(-16) * (z - 1/16) * z" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# The generating function has singularities at the roots of the leading coefficient polynomial\n", "diff.leading_coefficient().factor()" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "\\begin{math}\n", "\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[\\verb|log(z)| + 4\\verb|z*log(z)| + 8\\verb|z| + 36\\verb|z^2*log(z)| + 84\\verb|z^2|, 1 + 4\\verb|z| + 36\\verb|z^2|\\right]\n", "\\end{math}" ], "text/plain": [ "[log(z) + 4*z*log(z) + 8*z + 36*z^2*log(z) + 84*z^2, 1 + 4*z + 36*z^2]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# There is a basis with the following series expansions near the origin\n", "origin_basis = diff.local_basis_expansions(0, order = 3)\n", "show(origin_basis)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The generating function has series expansion 1 + 4*z + 36*z^2 + ... at the origin\n" ] } ], "source": [ "# At the origin, the power series element is the generating function\n", "# So the generating function is expressed in this basis with coordinates\n", "ini = [0,1]\n", "print(\"The generating function has series expansion {} + ... at the origin\".format(add([origin_basis[k] * ini[k] for k in range(2)])))" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "\\begin{math}\n", "\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[\\verb|log(z|\\phantom{\\verb!x!}\\verb|-|\\phantom{\\verb!x!}\\verb|1/16)| - 4\\verb|(z|\\phantom{\\verb!x!}\\verb|-|\\phantom{\\verb!x!}\\verb|1/16)*log(z|\\phantom{\\verb!x!}\\verb|-|\\phantom{\\verb!x!}\\verb|1/16)| - 8\\verb|(z|\\phantom{\\verb!x!}\\verb|-|\\phantom{\\verb!x!}\\verb|1/16)|, 1 - 4\\verb|(z|\\phantom{\\verb!x!}\\verb|-|\\phantom{\\verb!x!}\\verb|1/16)|\\right]\n", "\\end{math}" ], "text/plain": [ "[log(z - 1/16) - 4*(z - 1/16)*log(z - 1/16) - 8*(z - 1/16), 1 - 4*(z - 1/16)]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Expansions of a basis near the generating function singularity z=1/16\n", "show(diff.local_basis_expansions(1/16, order = 2))" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "\\begin{math}\n", "\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rr}\n", "\\verb|[+/-|\\phantom{\\verb!x!}\\verb|9.83e-19]|\\phantom{\\verb!x!}\\verb|+|\\phantom{\\verb!x!}\\verb|[+/-|\\phantom{\\verb!x!}\\verb|8.56e-19]*I| & \\verb|[-0.31830988618|\\phantom{\\verb!x!}\\verb|+/-|\\phantom{\\verb!x!}\\verb|3.80e-12]|\\phantom{\\verb!x!}\\verb|+|\\phantom{\\verb!x!}\\verb|[+/-|\\phantom{\\verb!x!}\\verb|3.98e-19]*I| \\\\\n", "\\verb|[-3.1415926536|\\phantom{\\verb!x!}\\verb|+/-|\\phantom{\\verb!x!}\\verb|1.03e-11]|\\phantom{\\verb!x!}\\verb|+|\\phantom{\\verb!x!}\\verb|[+/-|\\phantom{\\verb!x!}\\verb|3.42e-18]*I| & \\verb|[+/-|\\phantom{\\verb!x!}\\verb|1.50e-18]|\\phantom{\\verb!x!}\\verb|+|\\phantom{\\verb!x!}\\verb|[1.0000000000|\\phantom{\\verb!x!}\\verb|+/-|\\phantom{\\verb!x!}\\verb|3e-16]*I|\n", "\\end{array}\\right)\n", "\\end{math}" ], "text/plain": [ "[ [+/- 9.83e-19] + [+/- 8.56e-19]*I [-0.31830988618 +/- 3.80e-12] + [+/- 3.98e-19]*I]\n", "[ [-3.1415926536 +/- 1.03e-11] + [+/- 3.42e-18]*I [+/- 1.50e-18] + [1.0000000000 +/- 3e-16]*I]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# We can compute the change of basis matrix between the basis with series at the origin and the basis with series at 1/6\n", "# We take a low numeric accuracy here to fit on screen\n", "show(diff.numerical_transition_matrix([0,1/16],1e-10))" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "([-0.31830988618379067+/-2.14e-18]+[+/-2.98e-38]*I)*log(z - 1/16) + ([1.2732395447351627+/-2.54e-17]+[+/-1.19e-37]*I)*(z - 1/16)*log(z - 1/16) + ([2.5464790894703253+/-7.71e-17]+[-4.0000000000000000+/-4.17e-17]*I)*(z - 1/16) + ([+/-2.37e-30]+[1.0000000000000000+/-6.94e-18]*I)*1" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Thus the generating function has a singular expansion at z=1/16 which begins\n", "bas = diff.numerical_transition_matrix([0,1/16]) * vector(ini)\n", "loc = diff.local_basis_expansions(1/16,2)\n", "add([a*b for [a,b] in zip(bas,loc)])" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "([0.31830988618379067 +/- 2.14e-18])*16^n/n" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# The extraction [z^n]log(1-16z) = -16^n/n then implies the central binomial coefficients have asymptotic expansion\n", "var('n')\n", "bas[0].real() * (-16^n/n)" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.318309886183791" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# The connection constant is 1/pi\n", "(1/pi).n()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SageMath 9.2", "language": "sage", "name": "sagemath" }, "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.5" } }, "nbformat": 4, "nbformat_minor": 4 }