6 Polinomios.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Polinomios\n",
    "\n",
    "Para empezar a trabajar con polinomios, tenemos que especificar las variables y qué anillo de coeficientes vamos a considerar. `gap` por defecto expande las expresiones que introducimos. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "InstallMethod(ViewString,[IsPolynomial],String);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x:=Indeterminate(Rationals,\"x\");"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x^2-1"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(x+1)*(x-1);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si queremos obtener una lista de los coeficientes de un polinomio en una variable, podemos usar lo siguiente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ -1, 1, 0, 1 ]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "CoefficientsOfUnivariatePolynomial(x^3+x-1);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Y el coeficiente líder lo obtenemos con `LeadingCoefficient`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "LeadingCoefficient(x^3+x-1);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Definamos una función para encontrar el término líder de un polinomio respecto de una variable. En ella usamos funciones que son alternativa a las que acabamos de ver para más de una variable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "function( p, x ) ... end"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "terminolider:=function(p,x)\n",
    "    local grado;\n",
    "    grado:=DegreeIndeterminate(p,x);\n",
    "    return PolynomialCoefficientsOfPolynomial(p,x)[grado+1]*x^grado;\n",
    "end;\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x^2"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "terminolider(x^2+x-1,x);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3*x^2"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "terminolider(3*x^2+x-1,x);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "y"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y:=Indeterminate(Rationals,\"y\");"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x^2*y"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "terminolider(y*x^2+y^4*x-1,x);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "LeadingCoefficient(y*x^2+y^4*x-1);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ -1, y^4, y ]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "PolynomialCoefficientsOfPolynomial(y*x^2+y^4*x-1,x);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## División de polinomios\n",
    "\n",
    "Si el anillo de coeficientes que consideramos es un cuerpo, entonces sabemos que el anillo de polinomios sobre una sola variable es un dominio euclídeo. Por tanto, podemos usar las funciones que ya conocemos para calcular el cociente y resto de una división."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 1/2*x, 1/2*x+1 ]"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "QuotientRemainder(x^3-x+1,2*x^2-3);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si nuestro anillo de polinomios no es un dominio euclídeo, entonces no podemos usar estas funciones."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "no 2nd choice method found for `QuotientRemainder' on 3 argumentsAn error happened"
     ]
    }
   ],
   "source": [
    "QuotientRemainder((x^3-x+1)*(y-1),y-1);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ahora bien, si que podemos usar la función {\\tt Quotient} que nos da el cociente, en caso de que éste pertenezca a nuestro anillo de polinomio, y {\\tt fail} en caso contrario."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x^3-x+1"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Quotient((x^3-x+1)*(y-1),y-1);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x^3-x+1"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(x^3-x+1)*(y-1)/(y-1);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Factorización de polinomios"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si lo que queremos es factorizar polinomios, primero tenemos que definir la variable, e indicar cuál es el anillo de coeficientes para nuestros polinomios. Luego se usa `Factors`  igual que con enteros."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x:=Indeterminate(ZmodnZ(5),\"x\");"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u0003#I  \u0003\u0003Teaching mode is turned \u0003\u0003ON\u0003\u0003\n",
      "\u0003"
     ]
    }
   ],
   "source": [
    "TeachingMode();"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ x+ZmodnZObj(2,5), x+ZmodnZObj(3,5) ]"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Factors(x^2+1);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "TeachingMode(true);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ x+ZmodnZObj(2,5), x+ZmodnZObj(3,5) ]"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Factors(x^2+1);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x:=Indeterminate(Rationals,\"x\");"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ x^2+1 ]"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Factors(x^2+1);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lo mismo ocurre con las raices y con el hecho de ser irreducible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x:=Indeterminate(ZmodnZ(3),\"x\");"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ ZmodnZObj(1,3), ZmodnZObj(1,3), ZmodnZObj(1,3) ]"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "RootsOfUPol(x^3-1);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x:=Indeterminate(Rationals,\"x\");"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 1 ]"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "RootsOfUPol(x^3-1);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IsIrreducible(x^2+1);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x:=Indeterminate(ZmodnZ(2),\"x\");"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IsIrreducible(x^2+1);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Veamos ahora a modo de ejemplo cómo calcular todos los polinomios irreducibles hasta un determinado grado en un anillo finito. Empezamos definiendo una función que nos genere todos los polinomios hasta un determinado grado.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "function( n, x ) ... end"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "polshastagradomodm:=function(n,x)\n",
    "    local ps, R;\n",
    "    \n",
    "    R:=CoefficientsRing(DefaultRing(x));\n",
    "    if Size(R)=infinity then\n",
    "        return fail;\n",
    "    fi;\n",
    "    \n",
    "    if (n=0) then\n",
    "        return Elements(R);\n",
    "    fi;\n",
    "\n",
    "    ps:=polshastagradomodm(n-1,x);\n",
    "    return Set(Cartesian(ps,x^n*Elements(R)),Sum);\n",
    "end;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Así todos los polinomios en $\\mathbb{Z}_3$ de grado menor o igual que dos son:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x:=Indeterminate(ZmodnZ(3),\"x\");"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ ZmodnZObj(0,3), ZmodnZObj(1,3), -ZmodnZObj(1,3), x, x+ZmodnZObj(1,3), x-ZmodnZObj(1,3), -x, -x+ZmodnZObj(1,3), -x-ZmodnZObj(1,3), x^2, x^2+ZmodnZObj(1,3), x^2-ZmodnZObj(1,3), x^2+x, x^2+x+ZmodnZObj(1,3), x^2+x-ZmodnZObj(1,3), x^2-x, x^2-x+ZmodnZObj(1,3), x^2-x-ZmodnZObj(1,3), -x^2, -x^2+ZmodnZObj(1,3), -x^2-ZmodnZObj(1,3), -x^2+x, -x^2+x+ZmodnZObj(1,3), -x^2+x-ZmodnZObj(1,3), -x^2-x, -x^2-x+ZmodnZObj(1,3), -x^2-x-ZmodnZObj(1,3) ]"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "polshastagradomodm(2,x);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "De entre ellos podemos escoger los que son irreducibles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ x, x+ZmodnZObj(1,3), x-ZmodnZObj(1,3), -x, -x+ZmodnZObj(1,3), -x-ZmodnZObj(1,3), x^2+ZmodnZObj(1,3), x^2+x-ZmodnZObj(1,3), x^2-x-ZmodnZObj(1,3), -x^2-ZmodnZObj(1,3), -x^2+x+ZmodnZObj(1,3), -x^2-x+ZmodnZObj(1,3) ]"
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Filtered(polshastagradomodm(2,x), IsIrreducible);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Y si queremos quedarnos con un representante salvo asociados, podemos usar lo siguiente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ x, x+ZmodnZObj(1,3), x-ZmodnZObj(1,3), x^2+ZmodnZObj(1,3), x^2+x-ZmodnZObj(1,3), x^2-x-ZmodnZObj(1,3) ]"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Set(Filtered(polshastagradomodm(2,x), IsIrreducible), StandardAssociate);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Cociente por un ideal. Cuerpos finitos\n",
    "\n",
    "Intentemos calcular los divisores de cero y unidades del anillo cociente $R=\\mathbb{Z}_2[x]/(x^2+1)$. Empezamos definiendo nuestra variable y el módulo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    " x:=Indeterminate(ZmodnZ(2),\"x\");"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x^2+Z(2)^0"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "modulo:=x^2+1;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Definimos $\\mathbb{Z}_2[x]$, y luego hacemos el cociente por el ideal generado por `modulo`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "GF(2)[x]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P:=PolynomialRing(ZmodnZ(2),\"x\");"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<ring GF(2),(1),(x)>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R:=P/Ideal(P,[modulo]);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 0*(1), (x), (1), (1)+(x) ]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Elements(R);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<group with 1 generators>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Units(R);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ (x), (1) ]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Elements(Units(R));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x^2+x+Z(2)^0"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f:=x^2+x+1;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si nuestro polinomio es irreducible, también podemos utilizar `AlgebraicExtension`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<field of size 4>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S:=AlgebraicExtension(ZmodnZ(2),f);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En `gap` podemos usar cualquier cuerpo finito con el comando `GF`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "GF(3^2)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "K:=GF(9);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Size(K);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ Z(3^2) ]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "GeneratorsOfField(K);"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "GAP 4 (native)",
   "language": "gap",
   "name": "gap-native"
  },
  "language_info": {
   "codemirror_mode": "gap",
   "file_extension": ".g",
   "mimetype": "text/x-gap",
   "name": "GAP (native)",
   "nbconvert_exporter": "",
   "pygments_lexer": "gap",
   "version": "4.dev"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}