{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Computing with binomial ideals\n",
    "\n",
    "The following examples show how to compute associated primes of cellular ideals, cellular decompositions of binomial ideals and primary decompositions of binomial ideals.\n",
    "\n",
    "For further imformation see\n",
    "* David Eisenbud and Bernd Sturmfels, Binomial ideals, Duke Math. J., 84 (1996), No. 1, 1-45.\n",
    "* Thomas Kahle, Decompositions of binomial ideals, Ann. Inst. Statist. Math. 62 (2010), No. 4, 727-745.\n",
    "* Clara Petroll, Primary decompositions of binomial ideals, Bachelor Thesis, TU Kaiserslautern (2017).\n",
    "\n",
    "At current state, running this notebook requires an experimental version of OSCAR.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "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.3.0-dev \u001b[39m... \n",
      " ... which comes with absolutely no warranty whatsoever\n",
      "Type: '?Oscar' for more information\n",
      "(c) 2019-2020 by The Oscar Development Team\n"
     ]
    }
   ],
   "source": [
    "using Oscar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "Oscar.example(\"BinomIdeal2.jl\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\text{Abelian closure of }\\mathbb{Q}$"
      ],
      "text/plain": [
       "Abelian closure of Q"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Qab = QabField()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Associated Primes\n",
    "For cellular ideals we can compute the associated primes and the minimal associated primes.\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "($\\text{Multivariate Polynomial Ring in 6 variables:} [x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}]\\text{ over }\\text{Abelian closure of Q}$, [$x_{1}$, $x_{2}$, $x_{3}$, $x_{4}$, $x_{5}$, $x_{6}$])"
      ],
      "text/plain": [
       "(Multivariate Polynomial Ring in 6 variables x_{1}, x_{2}, x_{3}, x_{4}, ..., x_{6} over Abelian closure of Q, AbstractAlgebra.Generic.MPoly{Main.QabModule.QabElem}[x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R, x = PolynomialRing(Qab, :x => 1:6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\text{ideal generated by: }x_{1}x_{5}-x_{2}x_{5}, x_{3}x_{6}-x_{4}x_{6}, x_{5}^{2}, x_{6}^{2}, x_{5}x_{6}$"
      ],
      "text/plain": [
       "ideal generated by: x_{1}*x_{5}-x_{2}*x_{5}, x_{3}*x_{6}-x_{4}*x_{6}, x_{5}^2, x_{6}^2, x_{5}*x_{6}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "I = ideal([x[5]*(x[1]-x[2]),x[6]*(x[3]-x[4]),x[5]^2,x[6]^2,x[5]*x[6]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The ideal is {$1,2,3,4$}-cellular.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "(true, [$1$, $2$, $3$, $4$])"
      ],
      "text/plain": [
       "(true, [1, 2, 3, 4])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iscellular(I)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The witness monomials of embedded associated lattices to the ideal are the following.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "[$x_{5}$, $x_{6}$]"
      ],
      "text/plain": [
       "2-element Array{AbstractAlgebra.Generic.MPoly{Main.QabModule.QabElem},1}:\n",
       " x_{5}\n",
       " x_{6}"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Cellular.witness_monomials(I)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we compute the minimal associated primes, as well as the associated primes.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "[$\\text{ideal generated by: }x_{5}, x_{6}$]"
      ],
      "text/plain": [
       "1-element Array{Oscar.MPolyIdeal,1}:\n",
       " ideal generated by: x_{5}, x_{6}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Cellular.minimal_associated_primes(I)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "[$\\text{ideal generated by: }x_{5}, x_{6}$, $\\text{ideal generated by: }x_{1}-x_{2}, x_{5}, x_{6}$, $\\text{ideal generated by: }x_{3}-x_{4}, x_{5}, x_{6}$]"
      ],
      "text/plain": [
       "3-element Array{Oscar.MPolyIdeal,1}:\n",
       " ideal generated by: x_{5}, x_{6}             \n",
       " ideal generated by: x_{1}-x_{2}, x_{5}, x_{6}\n",
       " ideal generated by: x_{3}-x_{4}, x_{5}, x_{6}"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Cellular.associated_primes(I)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Cellular Decomposition\n",
    "We consider a noncellular ideal in a polynomial ring with three variables."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "($\\text{Multivariate Polynomial Ring in 3 variables:} [x, y, z]\\text{ over }\\text{Abelian closure of Q}$, [$x$, $y$, $z$])"
      ],
      "text/plain": [
       "(Multivariate Polynomial Ring in x, y, z over Abelian closure of Q, AbstractAlgebra.Generic.MPoly{Main.QabModule.QabElem}[x, y, z])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R, (x, y, z) = PolynomialRing(Qab, [\"x\", \"y\", \"z\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\text{ideal generated by: }x-y, x^{3}-1, y^{2}z-z$"
      ],
      "text/plain": [
       "ideal generated by: x-y, x^3-1, y^2*z-z"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "I = ideal([x-y,x^3-1,z*y^2-z])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In fact, the ideal is noncellular, which can be verified as follows:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "(false, $3$)"
      ],
      "text/plain": [
       "(false, 3)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iscellular(I)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The output means that the variable $z$ is a zerodivisor modulo $I$ but not nilpotent modulo $I$. Hence the ideal cannot be cellular. \n",
    "\n",
    "We now compute the decomposition of $I$ into cellular binomial ideals."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "[$\\text{ideal generated by: }y-1, x-1$, $\\text{ideal generated by: }x-y, x^{3}-1, y^{2}z-z, z$]"
      ],
      "text/plain": [
       "2-element Array{Oscar.MPolyIdeal,1}:\n",
       " ideal generated by: y-1, x-1              \n",
       " ideal generated by: x-y, x^3-1, y^2*z-z, z"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bcd = Cellular.decomposition(I)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The intersection is equal to the original ideal.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "true"
      ],
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bcd[1] ∩ bcd[2] == I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binomial primary decomposition\n",
    "To compute the primary decomposition of a binomial ideal $I$, the algorithm first decomposes $I$\n",
    "into cellular ideals as above and then computes for each of the cellular binomial ideals a binomial primary decomposition.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "[$\\text{ideal generated by: }z, y-\\zeta_{3}, x-\\zeta_{3}$, $\\text{ideal generated by: }z, y+(\\zeta_{3}+1), x+(\\zeta_{3}+1)$, $\\text{ideal generated by: }y-1, x-1$]"
      ],
      "text/plain": [
       "3-element Array{Oscar.MPolyIdeal,1}:\n",
       " ideal generated by: z, y-\\zeta_{3}, x-\\zeta_{3}        \n",
       " ideal generated by: z, y+(\\zeta_{3}+1), x+(\\zeta_{3}+1)\n",
       " ideal generated by: y-1, x-1                           "
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Binomial.primary_decomposition(I)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "@webio": {
   "lastCommId": null,
   "lastKernelId": null
  },
  "kernelspec": {
   "display_name": "Julia 1.3.1",
   "language": "julia",
   "name": "julia-1.3"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.3.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}