{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6a512e0d",
   "metadata": {},
   "source": [
    "# Computing Valuation Manually\n",
    "\n",
    "We wish to compute $\\textrm{ord}_P(f)$ where $P = (2, 4)$ and $f = y - 2x$.\n",
    "\n",
    "$$E(\\mathbb{F}_{11}) : y^2 = x^3 + 4x$$\n",
    "\n",
    "Let $K[V] = K[x, y] / \\langle y^2 - x^3 - 4x \\rangle$ by the coordinate ring. $K(V)$ is the field of fractions for $K[V]$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "5d554e0c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Fraction Field of Quotient of Multivariate Polynomial Ring in x, y over Finite Field of size 11 by the ideal (-x^3 + y^2 - 4*x)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Define our base polynomial ring over Z_11\n",
    "K.<x, y> = GF(11)[]\n",
    "# This is K(V)\n",
    "S = K.quotient(y^2 - x^3 - 4*x).fraction_field()\n",
    "S"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "69feb612",
   "metadata": {},
   "source": [
    "Because $P$ lies on the curve $E$, we can take the nontangent lines $x - 2, y - 4$ as a basis for the local curve. The intuition is that these lines describe the coordinate grid around $P$, and we can multiply them by any polynomial to get cosets of $K(V)$.\n",
    "\n",
    "More formally we can see this by noting that:\n",
    "\n",
    "$$(y - 4)(y + 4) = (x - 2)^3 - 5(x - 2)^2 - 6(x - 2)$$\n",
    "\n",
    "So therefore any function on $E$ can be expressed in terms of $(x - 2)$ and $(y - 4)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "c430ae30",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X, Y = S(x), S(y)\n",
    "(Y - 4)*(Y + 4) == (X - 2)^3 - 5*(X - 2)^2 - 6*(X - 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2515224a",
   "metadata": {},
   "source": [
    "Begin by expressing $f = y - 2x$ in terms of this basis.\n",
    "\\begin{align*}\n",
    "y &= y - 2x \\\\\n",
    "  &= -2(x - 2) + 1(y - 4) \\\\\n",
    "\\mathbf{a} &= (-2, 1, 0) \\\\\n",
    "\\mathbf{b} &= (x - 2, y - 4, 1)\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "bd415ef9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-2*x + y"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Components for f\n",
    "a0, a1, a2 = -2, 1, 0\n",
    "# Our basis\n",
    "b0, b1, b2 = x - 2, y - 4, 1\n",
    "a0*b0 + a1*b1 + a2*b2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e3087005",
   "metadata": {},
   "source": [
    "Using the identity above for $(y - 4)(y + 4)$, we can see that\n",
    "\\begin{align*}\n",
    "(y - 4) &= \\frac{(x - 2)^3 - 5*(x - 2)^2 - 6(x - 2)}{(y + 4)} \\\\\n",
    "        &= (x - 2) \\frac{(x - 2)^2 - 5*(x - 2) - 6}{(y + 4)}\n",
    "\\end{align*}\n",
    "So we can know that $b_1 = (E_f / E_g) b_0$, and can make this substitution in $f$.\n",
    "\\begin{align*}\n",
    "f &= -2 (x - 2) + 1 \\cdot \\frac{(x - 2)^3 - 5(x - 2)^2 - 6(x - 2)}{y + 4} \\\\\n",
    "  &= \\frac{1}{(y + 4)}[(x - 2)^3 - 5(x - 2)^2 - 6(x - 2) - 2(x - 2)(y + 4)]\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "9e2be279",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# and lets double check this\n",
    "B0 = X - 2\n",
    "Eg = Y + 4\n",
    "(B0^3 - 5*B0^2 - 6*B0 - 2*B0*Eg)/Eg == Y - 2*X"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9dfe225e",
   "metadata": {},
   "source": [
    "Now lets quotient out $b_0 = (x - 2)$ from $f$ to get the first power of $k = 1$ for the uniformizer.\n",
    "\\begin{align*}\n",
    "f &= \\frac{(x + 2)^1}{(y + 4)}[(x - 2)^2 - 5(x - 2) - 6 - 2(y + 4)]\n",
    "\\end{align*}\n",
    "Notice now the constant term is $- 6 - 2(y + 4)$ which should be a multiple of $y - 4$ if we can continue extracting $b_0$ from the expression."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "249b0ed0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-2*y - 3"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "-6 - 2*(y + 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "5894ffc4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-2*y - 3"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "-2*(y - 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dc5c6b41",
   "metadata": {},
   "source": [
    "Great so we continue. Instead of writing $-6 - 2(y + 4)$, lets instead write $-2(y - 4)$\n",
    "\\begin{align*}\n",
    "f &= \\frac{(x + 2)^1}{(y + 4)}[(x - 2)^2 - 5(x - 2) - 2(y - 4)] \\\\\n",
    "  &= \\frac{(x + 2)^1}{(y + 4)}[(x - 2)^2 - 5(x - 2) - 2\\frac{(x - 2)^3 - 5(x - 2)^2 - 6(x - 2)}{y + 4}] \\\\\n",
    "  &= \\frac{(x + 2)^1}{(y + 4)^2}[(x - 2)^2(y + 4) - 5(x - 2)(y + 4) - 2((x - 2)^3 - 5(x - 2)^2 - 6(x - 2))] \\\\\n",
    "  &= \\frac{(x + 2)^2}{(y + 4)^2}[(x - 2)(y + 4) - 5(y + 4) - 2((x - 2)^2 - 5(x - 2) - 6)] \\\\\n",
    "\\end{align*}\n",
    "So $k = 2$, and lets evaluate the constant terms."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "7b343008",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-5*y + 3"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "-5*(y + 4) - 2*(-6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "595834a3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-5*y - 2"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "-5*(y - 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8928eeda",
   "metadata": {},
   "source": [
    "Now there's a remainder left over so the expression terminates."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5575757f",
   "metadata": {},
   "source": [
    "# Implementation Details\n",
    "\n",
    "Several points of interest:\n",
    "\n",
    "* We don't need to keep track of $g$ although it's done for completeness.\n",
    "* For the uniformizer part, we just need to keep track of $k$.\n",
    "* The inner expression can be optimized just by looking at the constant term when viewed from $(x - 2)$. Although we are not doing that."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "a0a83e30",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(x - 2, y - 4, 1)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b0, b1, b2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "d042e184",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(-2, 1, 0)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Decompose polynomial function into basis components\n",
    "def decomp(f):\n",
    "    a0, r = f.quo_rem(b0)\n",
    "    a1, r = r.quo_rem(b1)\n",
    "    a2, r = r.quo_rem(b2)\n",
    "    return a0, a1, a2\n",
    "\n",
    "f = y - 2*x\n",
    "decomp(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "c804233f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-x^3 + y^2 - 4*x"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Px, Py = (2, 4)\n",
    "EC_A = 4\n",
    "# Calculate substitution polynomials\n",
    "Ef = b0^2 + binomial(3,2)*Px*b0^1 + (3*Px^2 + EC_A)\n",
    "Eg = (y + Py)\n",
    "# Should be EC equation\n",
    "Eg*b1 - Ef*b0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "cbbb63c7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(x^2 + 2*x - 2*y, y + 4)"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a0, a1, a2 = decomp(f)\n",
    "g = 1\n",
    "\n",
    "# Perform first reduction\n",
    "a0 = Eg*a0 + Ef*a1\n",
    "a1 = 0\n",
    "g *= Eg\n",
    "assert a1 == a2 == 0\n",
    "a0, g"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9357c553",
   "metadata": {},
   "source": [
    "Set $k = 1$ since we have now factored out $(x - 2)$. Continue for second decomposition followed by reduction."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "d5810612",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(x + 4, -2, 0)"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a0, a1, a2 = decomp(a0)\n",
    "a0, a1, a2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a5b3561",
   "metadata": {},
   "source": [
    "as expected the remainder a2 is zero"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "22671821",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U = (X - 2)\n",
    "F = (X + 4)*(X - 2) - 2*(Y - 4)\n",
    "G = Y + 4\n",
    "U^1 * F / G == Y - 2*X"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "411c7216",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(-2*x^2 + x*y + 4*y, y^2 - 3*y + 5)"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Second reduction\n",
    "a0 = Eg*a0 + Ef*a1\n",
    "a1 = 0\n",
    "g *= Eg\n",
    "assert a1 == a2 == 0\n",
    "a0, g"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "de5d1ed9",
   "metadata": {},
   "source": [
    "Set $k = 2$. Now decompose and check remainder is zero again before performing reduction."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "eceb52f7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(-2*x + y - 4, -5, 5)"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a0, a1, a2 = decomp(a0)\n",
    "a0, a1, a2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "daab41c5",
   "metadata": {},
   "source": [
    "Now the remainder is 5 so the algorithm stops. Our final valuation is $k = 2$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "1c654c46",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Convert our function to the function field K(V)\n",
    "original_f = Y - 2*X\n",
    "k = 2\n",
    "\n",
    "f = a0*b0 + a1*b1 + a2*b2\n",
    "fprime = b0^k * f/g\n",
    "assert fprime == S(original_f)\n",
    "assert g(Px, Py) != 0\n",
    "assert f(Px, Py) != 0\n",
    "assert b0(Px, Py) == 0\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d9a8af14",
   "metadata": {},
   "source": [
    "# Abstract Algebraic Method\n",
    "\n",
    "See Knapp page 350"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "ce94255a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True, False)"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R.<x> = FunctionField(GF(11)); _.<Y> = R[]\n",
    "K.<y> = R.extension(Y^2 - x^3 - 4*x)\n",
    "P = (2, 4)\n",
    "o = R.maximal_order()\n",
    "O = K.maximal_order()\n",
    "M = o.ideal(x - 2)\n",
    "# if I = <x - 2> then (x - 2) in I^2 is false \n",
    "x - 2 in M, x - 2 in M^2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "052087b6",
   "metadata": {},
   "source": [
    "Also verify that the point is ordinary (nonsingular)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "1a218ce1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M.is_prime()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "e737ac7f",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(Ideal (x + 9, y + 4) of Maximal order of Function field in y defined by y^2 + 10*x^3 + 7*x,\n",
       "  1,\n",
       "  1),\n",
       " (Ideal (x + 9, y + 7) of Maximal order of Function field in y defined by y^2 + 10*x^3 + 7*x,\n",
       "  1,\n",
       "  1)]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "O.decomposition(M)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "867a9f68",
   "metadata": {},
   "outputs": [],
   "source": [
    "# I can't seem to use M for f\n",
    "# This is a workaround until I find a fix\n",
    "M = O.ideal(x - 2, y - 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "2a10bcd6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True, True, False)"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f = y - 2*x\n",
    "f in M, f in M^2, f in M^3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "73406fd6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d = [i for i in range(1, 10) if f in M^i]\n",
    "max(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3b1b13e9",
   "metadata": {},
   "source": [
    "# Simple Method by Parameterizing\n",
    "\n",
    "We parameterize our line $f$ so that $(x(0), y(0)) = P$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "02ae75dc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10*t^3 + 9*t^2"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "K.<t> = GF(11)[]\n",
    "x = t + 2\n",
    "# y - 2x = 0\n",
    "# => y = 2x\n",
    "y = 2*x\n",
    "# Now just write equation in terms of parameterized x(t) and y(t)\n",
    "y^2 - x^3 - 4*x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7381d05b",
   "metadata": {},
   "source": [
    "As observed we have a uniformizer $t$ with $k = 2$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a05bc126",
   "metadata": {},
   "source": [
    "# Valuation with Places\n",
    "\n",
    "Using sage valuation rings since local ring is a DVR"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "3da404fc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Place (x, y),\n",
       " Place (x + 3, y + 4),\n",
       " Place (x + 3, y + 7),\n",
       " Place (x + 5, y + 3),\n",
       " Place (x + 5, y + 8),\n",
       " Place (x + 7, y + 5),\n",
       " Place (x + 7, y + 6),\n",
       " Place (x + 9, y + 4),\n",
       " Place (x + 9, y + 7),\n",
       " Place (x + 10, y + 4),\n",
       " Place (x + 10, y + 7)]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "K.<x> = FunctionField(GF(11))\n",
    "_.<Y> = K[]\n",
    "L.<y> = K.extension(Y^2 - x^3 - 4*x)\n",
    "L.places_finite()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e4719879",
   "metadata": {},
   "source": [
    "We are interested in $P = (2, 4)$ so we want the place $(x - 2, x - 4) = (x + 9, y + 7)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "f87c8b23",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Place (x + 9, y + 7)"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# I don't know how to actually construct this yet\n",
    "p = L.places_finite()[-3]\n",
    "p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "3d007b0b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(y - 2*x).valuation(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "021f9110",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 10.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.12.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}