{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 4.7 (An Infinite Group Model)\n", "Proving the group of a small step quadrant model is infinite. \n", "*Requirements: None*" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "X + Y + 1/X + 1/Y + 1/(X*Y)" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Define the step set under consideration and its characteristic polynomial\n", "var('x,y,X,Y')\n", "ST = [(-1,-1), (0,-1), (0,1), (1,0), (-1,0)]\n", "S = add(X^i*Y^j for [i,j] in ST)\n", "S" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{b: 1.324717957244746?, a: 1.324717957244746?}\n" ] } ], "source": [ "# First, we prove through direct computation that the group is infinite\n", "# Start by computing the unique stationary point with positive coordinates\n", "Sx = diff(S,X).numerator()\n", "Sy = diff(S,Y).numerator()\n", "R. = QQbar[]\n", "J = R.ideal(Sx(a,b),Sy(a,b))\n", "[stat] = [k for k in J.variety(QQbar) if a.subs(k)>0 and b.subs(k)>0]\n", "print(stat)" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(1/18*sqrt(23)*sqrt(3) + 1/2)^(1/3) + 1/3/(1/18*sqrt(23)*sqrt(3) + 1/2)^(1/3)" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# These algebraic coordinates are stored and manipulated exactly in Sage\n", "a.subs(stat).radical_expression()" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "\\begin{math}\n", "\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rr}\n", "-1 & -0.4301597090019468? \\\\\n", "0.4301597090019468? & -0.814962624751361?\n", "\\end{array}\\right)\n", "\\end{math}" ], "text/plain": [ "[ -1 -0.4301597090019468?]\n", "[ 0.4301597090019468? -0.814962624751361?]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Compute the Jacobian matrix of the map Θ(x,y) = Φ(Ψ(x,y)) at the stationary point (a,b)\n", "Am1 = S.coefficient(Y,-1); A0 = S.coefficient(Y,0); A1 = S.coefficient(Y,1)\n", "Bm1 = S.coefficient(X,-1); B0 = S.coefficient(X,0); B1 = S.coefficient(X,1)\n", "def Ψ(SS): return [L.subs(X=SS[0],Y=SS[1]).simplify() for L in [(1/X)*Bm1/B1,Y]]\n", "def Φ(SS): return [L.subs(X=SS[0],Y=SS[1]).simplify() for L in [X,(1/Y)*Am1/A1]]\n", "T = Φ(Ψ([x,y]))\n", "J = jacobian(T, (x,y)).subs(x=a.subs(stat),y=b.subs(stat))\n", "show(J)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[-0.907481312375681? + 0.4200924513591182?*I, -0.907481312375681? - 0.4200924513591182?*I]" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Compute the eigenvalues of the Jacobian\n", "eig = MatrixSpace(QQbar,2,2)(J).eigenvalues()\n", "eig" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[pi - arctan(0.4629213248032239?), -pi + arctan(0.4629213248032239?)]" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# The eigenvalues are not roots of unity, so the group of the model is infinite\n", "[arg(k) for k in eig]" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "-(L^6 + 8*L^5 + 28*L^4 + 41*L^3 + 28*L^2 + 8*L + 1)*(L^2 + 3*L + 1)^2*(L + 1)^2*L^2" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# ALTERNATIVELY, following the argument of the text the following computation gives an annihilating polynomial of the eigenvalues\n", "var('L')\n", "eq1 = (L^2 - (1/(1+x)/(1+y)-2)*L+1).numerator()\n", "eq2 = Sx(x,y)\n", "eq3 = Sy(x,y)\n", "res = eq1.resultant(eq2,x).resultant(eq1.resultant(eq3,x),y).factor()\n", "res" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[-2.618033988749895?,\n", " -1,\n", " -0.3819660112501051?,\n", " 0,\n", " -2.874631498544436? - 2.220293676030299?*I,\n", " -2.874631498544436? + 2.220293676030299?*I,\n", " -0.907481312375681? - 0.4200924513591182?*I,\n", " -0.907481312375681? + 0.4200924513591182?*I,\n", " -0.2178871890798835? - 0.1682906307285094?*I,\n", " -0.2178871890798835? + 0.1682906307285094?*I]" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Of course, the roots of this polynomial includes the two eigenvalues as computed above\n", "QQbar['L'](res).roots(multiplicities=False)" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[L - 1,\n", " L + 1,\n", " L^2 + L + 1,\n", " L^2 + 1,\n", " L^4 + L^3 + L^2 + L + 1,\n", " L^2 - L + 1,\n", " L^6 + L^5 + L^4 + L^3 + L^2 + L + 1,\n", " L^4 + 1,\n", " L^6 + L^3 + 1,\n", " L^4 - L^3 + L^2 - L + 1,\n", " L^4 - L^2 + 1,\n", " L^6 - L^5 + L^4 - L^3 + L^2 - L + 1,\n", " L^6 - L^3 + 1]" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Standard bounds (for instance, Thm 8.8.7 in Bach and Shallit, Algorithmic Number Theory Vol. 1, 1996) on the degrees\n", "# of cyclotomic polynomials imply any cyclotomic polynomial of degree <= 6 has index < 30. Thus the group is\n", "# infinite as long as the degree six factor of the polynomial res above is not in the following list.\n", "from sage.rings.polynomial.cyclotomic import cyclotomic_coeffs\n", "P = QQ['L']\n", "[P.cyclotomic_polynomial(k) for k in range(1,30) if P.cyclotomic_polynomial(k).degree() <= 6]" ] }, { "cell_type": "code", "execution_count": 0, "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 }