pcom:

{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# OSCAR, a Tech Preview (Part II)\n", "## Wronski Polynomial Systems\n", "\n", "This example features polytopes and polynomials. For further details see the following articles (and their references).\n", "\n", "* Joswig & Ziegler: Foldable triangulations of lattice polygons, Amer. Math. Monthly 121/8 (2014).\n", "* Kaluba, Lorenz & Timme: Polymake.jl: A new interface to polymake, arXiv:2003.11381\n", "* Soprunova & Sottile: Lower bounds for real solutions to sparse polynomial systems, Adv. Math. 204 (2006).\n", "\n", "Our goal is to illustrate Theorem 3.5 in the article by Soprunova & Sottile by an example." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "polymake: WARNING: Recompiling in /home/mic/.julia/polymake_user/wrappers.0/build/Opt, please be patient...\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ " ----- ----- ----- - ----- \n", "| | | | | | | | | | \n", "| | | | | | | | \n", "| | ----- | | | |----- \n", "| | | | |-----| | | \n", "| | | | | | | | | | \n", " ----- ----- ----- - - - - \n", "\n", "...combining (and extending) ANTIC, GAP, Polymake and Singular\n", "Version\u001b[32m 0.5.1 \u001b[39m... \n", " ... which comes with absolutely no warranty whatsoever\n", "Type: '?Oscar' for more information\n", "(c) 2019-2021 by The Oscar Development Team\n" ] }, { "data": { "text/plain": [ "Polymake" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "using Oscar\n", "const pm=Polymake" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We will consider certain systems of polynomial equations which require a regular triangulation of a lattice polytope as (part of its) input." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "A = pm.polytope.lattice_points(pm.polytope.simplex(2,3))\n", "λ = [12,3,0,0,8,1,0,9,5,15];\n", "F = pm.polytope.regular_subdivision(A, λ)\n", "TT = pm.fan.SubdivisionOfPoints(POINTS = A, MAXIMAL_CELLS = F);" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "pm.display_svg(TT)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This triangulation is very special in that it is foldable (or \"balanced\"), i.e., the dual graph is bipartite. This means that the triangles can be colored, say, black and white such that no two triangles of the same color share an edge. The signature is the absolute difference of the black triangles minus the white triangles (of odd normalized volume)." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "T.FOLDABLE = true\n", "T.SIGNATURE = 3\n" ] }, { "data": { "text/html": [ "$3$" ], "text/plain": [ "3" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "T = pm.topaz.GeometricSimplicialComplex(COORDINATES = A[:,2:end], FACETS = F)\n", "@show T.FOLDABLE\n", "@show T.SIGNATURE" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It is a fact that the vertices of a foldable triangulation can be colored by $d+1$ colors (such that vertices of the same color do not share an edge), where $d$ is the dimension. Here $d=2$.\n", "\n", "The implementation uses HomotopyContinuation and polymake. The function below is used for converting polynomials." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "import HomotopyContinuation\n", "const HC=HomotopyContinuation\n", "\n", "function hc_poly(f, vars)\n", " M = pm.monomials_as_matrix(f)\n", " monomials_as_matrix = [prod(vars.^m) for m in eachrow(M)]\n", " coeffs = convert.(Int, pm.coefficients_as_vector(f))\n", " sum(map(*, coeffs, monomials_as_matrix))\n", "end;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now a Wronski polynomial has the given lattice points as exponents, and only one coefficient per color class of vertices of the triangulation.\n", "\n", "A Wronski system consists of $d$ Wronski polynomials with respect to the same lattice points and triangulation. It is assumed that the coefficients are generic.\n", "\n", "The Wronski center ideal is relevant for checking a necessary condition for that Theorem 3.5 of Soprunova & Sottile. This involves the triangulation and some lifting function. " ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3-element Array{DynamicPolynomials.Polynomial{true,Int64},1}:\n", " x₁³s¹⁵ + s¹² + x₁x₂s + x₂³\n", " x₁²s⁹ + x₂s³ + x₁x₂²\n", " x₁s⁸ + x₁²x₂s⁵ + x₂²" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "I = pm.polytope.wronski_center_ideal(A, λ)\n", "HC.@polyvar x[1:2] s;\n", "HC_I = [hc_poly(f, [x;s]) for f in I.GENERATORS]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The Wronski center ideal is generated by $d+1$, here 3, polynomials which collect the terms of the color classes and a new variable, $s$, for the lifting function." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\u001b[32mTracking 54 paths... 100%|██████████████████████████████| Time: 0:00:05\u001b[39m\n", "\u001b[34m # paths tracked: 54\u001b[39m\n", "\u001b[34m # non-singular solutions (real): 54 (2)\u001b[39m\n", "\u001b[34m # singular endpoints (real): 0 (0)\u001b[39m\n", "\u001b[34m # total solutions (real): 54 (2)\u001b[39m\n", " 22.855212 seconds (60.34 M allocations: 2.947 GiB, 2.85% gc time)\n" ] }, { "data": { "text/plain": [ "Result with 54 solutions\n", "========================\n", "• 54 paths tracked\n", "• 54 non-singular solutions (2 real)\n", "• random_seed: 0xefb37c3b\n", "• start_system: :polyhedral\n" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@time res = HC.solve(HC_I; start_system = :polyhedral, only_torus = true)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We get 54 complex roots, out of which two are real. One of the conditions to check asks that there are no real roots between $0$ and $1$. See the Soprunova-Sottile paper for details." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-element Array{Array{Float64,1},1}:\n", " [-0.21175800954334498, -215.7226007931453, 4.411470567441928]\n", " [-0.6943590430596772, -0.41424188458258865, -0.8952189506082182]" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "points = HC.real_solutions(res)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The main result of Soprunova & Sottile says that, if all the conditions are satisfied, then a Wronski system has at least signature many real solutions. In this case: 3." ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\r", "\u001b[32mTracking 9 paths... 100%|███████████████████████████████| Time: 0:00:02\u001b[39m\r\n", "\u001b[34m # paths tracked: 9\u001b[39m\r\n", "\u001b[34m # non-singular solutions (real): 9 (3)\u001b[39m\r\n", "\u001b[34m # singular endpoints (real): 0 (0)\u001b[39m\r\n", "\u001b[34m # total solutions (real): 9 (3)\u001b[39m\n" ] }, { "data": { "text/plain": [ "Result with 9 solutions\n", "=======================\n", "• 9 paths tracked\n", "• 9 non-singular solutions (3 real)\n", "• random_seed: 0x5b02c35c\n", "• start_system: :polyhedral\n" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "c = Vector{pm.Rational}[[19,8,-19], [39,7,42]];\n", "W = pm.polytope.wronski_system(A, λ, c, 1)\n", "HC_W = [hc_poly(f, x) for f in W.GENERATORS];\n", "W_res = HC.solve(HC_W)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Visualization" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Julia has powerful libraries for visualization. Here we are using ImplicitPlots to see the three points of intersection," ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "using ImplicitPlots, Plots\n", "p = plot(legend=false);\n", "\n", "implicit_plot!(p, HC_W[1]);\n", "implicit_plot!(p, HC_W[2]; linecolor=:red);\n", "p" ] } ], "metadata": { "kernelspec": { "display_name": "Julia 1.5.3", "language": "julia", "name": "julia-1.5" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.5.3" } }, "nbformat": 4, "nbformat_minor": 2 }