{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "## Example 7.7 (Apéry Critical Points)\n", "First, we see how to compute critical points for the Apéry example (in the [1,1,1,1] direction) using Gröbner bases.\n", "\n", "*Requirements: None*" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Ideal (-x^2*y^2*z^2*w - x^2*y^2*z*w - x^2*y*z^2*w - x^2*y*z*w - 2*x*y^2*z^2*w - 3*x*y^2*z*w - x*y^2*w - 3*x*y*z^2*w - 5*x*y*z*w - 2*x*y*w - x*z^2*w - 2*x*z*w - x*w - y^2*z^2*w - 2*y^2*z*w - y^2*w - 2*y*z^2*w - 4*y*z*w - 2*y*w - z^2*w - 2*z*w - w + 1, -x^2*y*z^2*w - x^2*y*z*w + 2*x*y^2*z^2*w + 3*x*y^2*z*w + x*y^2*w - x*z^2*w - 2*x*z*w - x*w + 2*y^2*z^2*w + 4*y^2*z*w + 2*y^2*w + 2*y*z^2*w + 4*y*z*w + 2*y*w, -x^2*y^2*z*w - x^2*y*z*w + 2*x*y^2*z^2*w - x*y^2*w + 3*x*y*z^2*w - 2*x*y*w + x*z^2*w - x*w + 2*y^2*z^2*w + 2*y^2*z*w + 4*y*z^2*w + 4*y*z*w + 2*z^2*w + 2*z*w, -x^2*y^2*z^2*w - x^2*y^2*z*w - x^2*y*z^2*w - x^2*y*z*w + y^2*z^2*w + 2*y^2*z*w + y^2*w + 2*y*z^2*w + 4*y*z*w + 2*y*w + z^2*w + 2*z*w + w) of Multivariate Polynomial Ring in x, y, z, w over Rational Field" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Set basic info for this example\n", "var('w,x,y,z')\n", "vars = [x,y,z,w]\n", "H = 1 - w*(1 + x)*(1 + y)*(1 + z)*(x*y*z + y*z + y + z + 1)\n", "\n", "# Form the critical point system\n", "C = [H] + [x * diff(H,x) - v *diff(H,v) for v in vars[1:]]\n", "\n", "# Convert this to an ideal in Sage\n", "L = PolynomialRing(QQ,4,'x,y,z,w',order='lex')\n", "I = L.ideal([L(k) for k in C])\n", "I" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "\\begin{math}\n", "\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[x - \\frac{1}{58} w - \\frac{70}{29}, y - \\frac{1}{116} w - \\frac{41}{58}, z - \\frac{1}{116} w - \\frac{41}{58}, w^{2} + 164 w - 4\\right]\n", "\\end{math}" ], "text/plain": [ "[x - 1/58*w - 70/29, y - 1/116*w - 41/58, z - 1/116*w - 41/58, w^2 + 164*w - 4]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Compute a Gröbner basis for this example, which can be\n", "# easily solved to get the critical points\n", "show(I.groebner_basis())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Example 7.8 (An Extended Critical Point System)\n", "We now compute with the extended critical point system for the Apéry example (in the *new direction* [2,1,1,1])\n", "\n", "*Requirements: None*" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Ideal (-w*x^2*y^2*z^2 - w*x^2*y^2*z - w*x^2*y*z^2 - w*x^2*y*z - 2*w*x*y^2*z^2 - 3*w*x*y^2*z - w*x*y^2 - 3*w*x*y*z^2 - 5*w*x*y*z - 2*w*x*y - w*x*z^2 - 2*w*x*z - w*x - w*y^2*z^2 - 2*w*y^2*z - w*y^2 - 2*w*y*z^2 - 4*w*y*z - 2*w*y - w*z^2 - 2*w*z - w + 1, -2*λ - w*x^2*y^2*z^2 - w*x^2*y^2*z - w*x^2*y*z^2 - w*x^2*y*z - 2*w*x*y^2*z^2 - 3*w*x*y^2*z - w*x*y^2 - 3*w*x*y*z^2 - 5*w*x*y*z - 2*w*x*y - w*x*z^2 - 2*w*x*z - w*x - w*y^2*z^2 - 2*w*y^2*z - w*y^2 - 2*w*y*z^2 - 4*w*y*z - 2*w*y - w*z^2 - 2*w*z - w, -λ - 2*w*x^2*y^2*z^2 - 2*w*x^2*y^2*z - 2*w*x^2*y*z^2 - 2*w*x^2*y*z - 2*w*x*y^2*z^2 - 3*w*x*y^2*z - w*x*y^2 - 3*w*x*y*z^2 - 5*w*x*y*z - 2*w*x*y - w*x*z^2 - 2*w*x*z - w*x, -λ - 2*w*x^2*y^2*z^2 - 2*w*x^2*y^2*z - w*x^2*y*z^2 - w*x^2*y*z - 4*w*x*y^2*z^2 - 6*w*x*y^2*z - 2*w*x*y^2 - 3*w*x*y*z^2 - 5*w*x*y*z - 2*w*x*y - 2*w*y^2*z^2 - 4*w*y^2*z - 2*w*y^2 - 2*w*y*z^2 - 4*w*y*z - 2*w*y, -λ - 2*w*x^2*y^2*z^2 - w*x^2*y^2*z - 2*w*x^2*y*z^2 - w*x^2*y*z - 4*w*x*y^2*z^2 - 3*w*x*y^2*z - 6*w*x*y*z^2 - 5*w*x*y*z - 2*w*x*z^2 - 2*w*x*z - 2*w*y^2*z^2 - 2*w*y^2*z - 4*w*y*z^2 - 4*w*y*z - 2*w*z^2 - 2*w*z, -w*x^2*y^2*z^2*t^7 - w*x^2*y^2*z*t^6 - w*x^2*y*z^2*t^6 - w*x^2*y*z*t^5 - 2*w*x*y^2*z^2*t^6 - 3*w*x*y^2*z*t^5 - w*x*y^2*t^4 - 3*w*x*y*z^2*t^5 - 5*w*x*y*z*t^4 - 2*w*x*y*t^3 - w*x*z^2*t^4 - 2*w*x*z*t^3 - w*x*t^2 - w*y^2*z^2*t^5 - 2*w*y^2*z*t^4 - w*y^2*t^3 - 2*w*y*z^2*t^4 - 4*w*y*z*t^3 - 2*w*y*t^2 - w*z^2*t^3 - 2*w*z*t^2 - w*t + 1) of Multivariate Polynomial Ring in λ, w, x, y, z, t over Rational Field" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Set basic info for this example\n", "var('w,x,y,z,λ,t')\n", "vars = [w,x,y,z]\n", "r = [2,1,1,1]\n", "H = 1 - w*(1 + x)*(1 + y)*(1 + z)*(x*y*z + y*z + y + z + 1)\n", "\n", "# Form the extended critical point system\n", "E = [H] + [vars[k] * diff(H,vars[k]) - r[k] * λ for k in range(len(vars))] + [H.subs([v==t*v for v in vars])]\n", "\n", "# Convert this to an ideal in Sage\n", "M = PolynomialRing(QQ,6,'λ,w,x,y,z,t',order='lex')\n", "I = M.ideal([M(k) for k in E])\n", "I" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(1/324) * (t - 1) * (324*t^18 + 1728*t^17 + 3105*t^16 + 9489*t^15 + 8461*t^14 - 66827*t^13 - 84029*t^12 - 419086*t^11 + 680942*t^10 - 1558672*t^9 + 3739659*t^8 + 3302612*t^7 - 5081362*t^6 - 4058824*t^5 + 309952*t^4 + 1599568*t^3 - 1073504*t^2 + 2989728*t + 20736)" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Compute a Gröbner basis, and print the elimination poly S(t) in t\n", "GB = I.groebner_basis()\n", "S = GB[-1]\n", "S.factor()" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "t^18 + 16/3*t^17 + 115/12*t^16 + 3163/108*t^15 + 8461/324*t^14 - 66827/324*t^13 - 84029/324*t^12 - 209543/162*t^11 + 340471/162*t^10 - 389668/81*t^9 + 1246553/108*t^8 + 825653/81*t^7 - 2540681/162*t^6 - 1014706/81*t^5 + 77488/81*t^4 + 399892/81*t^3 - 268376/81*t^2 + 83048/9*t + 64" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Define the large factor R(t) of S(t)\n", "R = (S/(t-1)).simplify_full()\n", "R" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[(λ,), (w, z), (x, z), (y, z), (z,), (z, t), (t,)]" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# This Gröbner basis is not in triangular form\n", "[p.variables() for p in GB]" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[λ + 1/2, w + 249/4*z^2 - 2785/24*z + 1057/36, x + 3/2*z^2 - 3/4*z - 3/4, y - z, z^3 - 7/6*z^2 - 5/6*z + 1/3, t - 1]" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# If we add the polynomial t-1 to the ideal, we get the \n", "# solutions corresponding to critical points\n", "(I + M.ideal([M(t-1)])).groebner_basis()" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[(λ,), (w, t), (x, t), (y, t), (z, t), (t,)]" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# If we add the large factor R(t) we get a more complicated \n", "# system, but it is in triangular form\n", "GB2 = (I + M.ideal([M(R)])).groebner_basis()\n", "[p.variables() for p in GB2]" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Polynomial degrees: [17, 17, 17]\n", "Max coefficient digit length: [55, 55, 55]\n" ] } ], "source": [ "# We end by printing the degrees and coefficient sizes for the \n", "# polynomials defining x,y, and z in terms of t\n", "def rat_bit_size(p):\n", " L = [abs(k.numerator()) for k in p.coefficients()] + [abs(k.denominator()) for k in p.coefficients()]\n", " return log(max(L),10).round()\n", "\n", "print(\"Polynomial degrees: \",[k.degree() for k in GB2[2:-1]])\n", "print(\"Max coefficient digit length: \", [rat_bit_size(k) for k in GB2[2:-1]])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Example 7.9 (Large Coefficient Sizes in a Univariate Representation)\n", "We encode the extended critical point system for the Apéry example (in the direction [2,1,1,1]) by a linear form u in the variables.\n", "\n", "*Requirements: None*" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": [ "# Set basic info for this example\n", "var('w,x,y,z,λ,t,u')\n", "vars = [w,x,y,z]\n", "r = [2,1,1,1]\n", "H = 1 - w*(1 + x)*(1 + y)*(1 + z)*(x*y*z + y*z + y + z + 1)\n", "\n", "# Form the extended critical point system\n", "E = [H] + [vars[k] * diff(H,vars[k]) - r[k] * λ for k in range(len(vars))] + [H.subs([v==t*v for v in vars])]\n", "\n", "# Add the linear form u = t + x\n", "E = E + [u-t-x]\n", "\n", "# Convert this to an ideal in Sage\n", "M = PolynomialRing(QQ,7,'λ,w,x,y,z,t,u',order='lex')\n", "I = M.ideal([M(k) for k in E])\n", "GB = I.groebner_basis()" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[(λ,), (w, u), (x, u), (y, u), (z, u), (t, u), (u,)]\n" ] }, { "data": { "text/plain": [ "(1/2902376448) * (12*u^3 - 19*u^2 - 10*u + 8) * (241864704*u^18 + 3345795072*u^17 + 21369754368*u^16 + 92838534912*u^15 + 337834871280*u^14 + 1051608329928*u^13 + 2617295811813*u^12 + 4911318707544*u^11 + 5774357518452*u^10 - 503520253323*u^9 - 18653245199288*u^8 - 42468890898735*u^7 - 49451567523618*u^6 - 5425655809061*u^5 + 74101038753291*u^4 + 83418755993667*u^3 + 5275556811046*u^2 - 26574394429140*u - 8505500275728)" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Now we have parametrized the solutions by u satisfying an explicit polynomial\n", "print([p.variables() for p in GB])\n", "GB[-1].factor()" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 1, 1, 1, 1]\n", "[1, 1, 1, 1, 1]\n" ] } ], "source": [ "# As expected, each of w,x,y,z, and t are defined by linear polynomials in u\n", "print([SR(p).degree(v) for (p,v) in zip(GB[1:6],[w,x,y,z,t])])\n", "print([SR(p).leading_coeff(v) for (p,v) in zip(GB[1:6],[w,x,y,z,t])])" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Polynomial degrees: [20, 20, 20, 20]\n", "Max coefficient digit length: [158, 159, 159, 158]\n" ] } ], "source": [ "# We end by printing the degrees and coefficient sizes for the \n", "# polynomials defining x,y,z, and t in terms of u\n", "print(\"Polynomial degrees: \",[k.degree() for k in GB[2:-1]])\n", "print(\"Max coefficient digit length: \", [rat_bit_size(k) for k in GB[2:-1]])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Example 7.10 (A Kronecker Representation)\n", "We encode the previous example with a Kronecker representation, and observe a decrease in coefficient sizes.\n", "\n", "*Requirements: None*" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [], "source": [ "# Set basic info for this example\n", "var('w,x,y,z,λ,t,u')\n", "vars = [w,x,y,z,λ,t]\n", "r = [2,1,1,1]\n", "H = 1 - w*(1 + x)*(1 + y)*(1 + z)*(x*y*z + y*z + y + z + 1)\n", "\n", "# Form the extended critical point system\n", "E = [H] + [vars[k] * diff(H,vars[k]) - r[k] * λ for k in range(4)] + [H.subs([v==t*v for v in vars])]\n", "\n", "# Add the linear form u = t + x\n", "E = E + [u-t-x]\n", "\n", "# Convert this to an ideal in Sage\n", "M = PolynomialRing(QQ,7,'λ,w,x,y,z,t,u',order='lex')\n", "I = M.ideal([M(k) for k in E])\n", "GB = I.groebner_basis()" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": [ "# Compute the Q polynomials for the Kronecker representation from the Gröbner basis\n", "P = GB[-1]\n", "Pd = diff(P,M(u))\n", "Q = {}\n", "for v in vars:\n", " [Qv] = list(filter(lambda p: SR(p).has(v), GB))\n", " _,Q[v] = QQ[u](Pd * v.subs(solve(SR(Qv),v))).quo_rem(P)\n", "sys = [SR(Q[v]/Pd) for v in vars]" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Polynomial degrees: [20, 20, 20, 20, 20, 20]\n", "Max coefficient digit length: [20, 16, 16, 16, 16, 16]\n" ] } ], "source": [ "# The polynomial degrees appearing are the same as the last example,\n", "# but the coefficient lengths are much decreased\n", "print(\"Polynomial degrees: \",[Q[v].degree() for v in vars])\n", "print(\"Max coefficient digit length: \", [rat_bit_size(Q[v]) for v in vars])" ] }, { "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": 2 }