{
  "cells": [
    {
      "cell_type": "markdown",
      "id": "sage-00",
      "metadata": {},
      "source": [
        "# Lab 4: Möbius maps, Lagrange, and Galois\n",
        "\n",
        "Use the **SageMath kernel** and run from the top. This lab accompanies\n",
        "Chapter 3, especially §§3.7–3.9. Each calculation uses exact integers,\n",
        "rational numbers, or quadratic fields. A finite experiment is evidence;\n",
        "the proof prompts ask for the argument that works for every input.\n",
        "\n",
        "The companion `.sage` file contains the same cells and can be run with\n",
        "`sage 04_mobius_lagrange_galois.sage`.\n"
      ]
    },
    {
      "cell_type": "code",
      "id": "sage-01",
      "metadata": {},
      "source": [
        "def digit_matrix(a):\n",
        "    return matrix(ZZ, [[a, 1], [1, 0]])\n",
        "\n",
        "def word_matrix(word):\n",
        "    M = identity_matrix(ZZ, 2)\n",
        "    for a in word:\n",
        "        M *= digit_matrix(a)\n",
        "    return M\n",
        "\n",
        "def mobius(M, x):\n",
        "    a, b, c, d = M.list()\n",
        "    if c*x + d == 0:\n",
        "        raise ValueError(\"The Möbius map has a pole at this input.\")\n",
        "    return (a*x + b)/(c*x + d)\n",
        "\n",
        "R = PolynomialRing(QQ, 't')\n",
        "t = R.gen()\n",
        "\n",
        "def fixed_polynomial(M):\n",
        "    a, b, c, d = M.list()\n",
        "    return c*t^2 + (d-a)*t - b\n",
        "\n",
        "word = [4, 2, 6, 7]  # 415/93\n",
        "M = word_matrix(word)\n",
        "assert M == matrix(ZZ, [[415, 58], [93, 13]])\n",
        "assert M.det() == (-1)^len(word)\n",
        "assert 13*415 - 58*93 == 1\n",
        "print(\"Convergent columns:\\n\", M)\n",
        "print(\"Integral inverse:\\n\", M.inverse())\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "id": "sage-02",
      "metadata": {},
      "source": [
        "## 1. Composition and the alternating trap\n",
        "\n",
        "A matrix acts by $T_M(t)=(at+b)/(ct+d)$. Verify composition with the\n",
        "**rightmost factor acting first**. Its derivative is\n",
        "$\\det(M)/(ct+d)^2$ wherever the denominator is nonzero.\n",
        "\n",
        "**Prove.** Derive the composition rule by multiplying two fractions.\n",
        "Use the determinant sign to recover the alternating inequalities for\n",
        "consecutive convergents. Explain why the pole must be excluded.\n"
      ]
    },
    {
      "cell_type": "code",
      "id": "sage-03",
      "metadata": {},
      "source": [
        "A, B = digit_matrix(3), digit_matrix(5)\n",
        "z = QQ(7)/4\n",
        "assert mobius(A*B, z) == mobius(A, mobius(B, z))\n",
        "F = R.fraction_field()\n",
        "a, b, c, d = M.list()\n",
        "f = F(a*t+b)/F(c*t+d)\n",
        "assert f.derivative() == F(M.det())/F((c*t+d)^2)\n",
        "print(\"Derivative:\", f.derivative())\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "id": "sage-04",
      "metadata": {},
      "source": [
        "## 2. A periodic tail is a fixed point\n",
        "\n",
        "For $\\sqrt3=[1;\\overline{1,2}]$, the repeating tail is\n",
        "$x=(1+\\sqrt3)/2$. Its period matrix is $N=D(1)D(2)$.\n",
        "The prefix $D(1)$ takes $x$ to $\\sqrt3$, so conjugating $N$ by the\n",
        "prefix gives a matrix fixing $\\sqrt3$.\n",
        "\n",
        "**Prove.** Show that a nonscalar rational matrix fixing an irrational\n",
        "number gives a genuine quadratic equation. What fails for the identity?\n"
      ]
    },
    {
      "cell_type": "code",
      "id": "sage-05",
      "metadata": {},
      "source": [
        "K = QuadraticField(3, 'r')\n",
        "r = K.gen()\n",
        "x = (1+r)/2\n",
        "N = word_matrix([1, 2])\n",
        "prefix = digit_matrix(1)\n",
        "C = prefix*N*prefix.inverse()\n",
        "assert mobius(N, x) == x\n",
        "assert mobius(prefix, x) == r\n",
        "assert mobius(C, r) == r\n",
        "assert fixed_polynomial(N)(x) == 0\n",
        "assert fixed_polynomial(C)(r) == 0\n",
        "assert fixed_polynomial(identity_matrix(ZZ, 2)) == 0\n",
        "print(\"Tail equation:\", fixed_polynomial(N))\n",
        "print(\"Conjugated matrix:\\n\", C)\n",
        "print(\"Equation for sqrt(3):\", fixed_polynomial(C))\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "id": "sage-06",
      "metadata": {},
      "source": [
        "## 3. Lagrange's theorem: find the repeated state\n",
        "\n",
        "For $x_n=(P_n+\\sqrt D)/Q_n$, record the complete quotient, not a\n",
        "rounded decimal. Starting with $\\sqrt D$, the recurrence is\n",
        "$P_{n+1}=a_nQ_n-P_n$ and $Q_{n+1}=(D-P_{n+1}^2)/Q_n$.\n",
        "We stop at the **first repeated pair** $(P_n,Q_n)$; we do not assume\n",
        "a period length or a final digit in advance.\n"
      ]
    },
    {
      "cell_type": "code",
      "id": "sage-07",
      "metadata": {},
      "source": [
        "def sqrt_states(D):\n",
        "    D = ZZ(D)\n",
        "    if D <= 0 or D.is_square():\n",
        "        raise ValueError(\"D must be a positive nonsquare integer.\")\n",
        "    a0 = D.isqrt()\n",
        "    P, Q = ZZ(0), ZZ(1)\n",
        "    seen, rows = {}, []\n",
        "    while (P, Q) not in seen:\n",
        "        seen[P, Q] = len(rows)\n",
        "        a = (P+a0)//Q\n",
        "        rows.append((P, Q, a))\n",
        "        nextP = a*Q-P\n",
        "        assert (D-nextP^2) % Q == 0\n",
        "        P, Q = nextP, (D-nextP^2)//Q\n",
        "    start = seen[P, Q]\n",
        "    return rows[:start], rows[start:]\n",
        "\n",
        "for D in [2, 3, 7, 13, 23, 41, 61]:\n",
        "    prefix_rows, cycle = sqrt_states(D)\n",
        "    root = QuadraticField(D, 'r').gen()\n",
        "    cf = continued_fraction(root)\n",
        "    assert tuple(row[2] for row in prefix_rows) == cf.preperiod()\n",
        "    assert tuple(row[2] for row in cycle) == cf.period()\n",
        "    print(\"D =\", D, \"prefix =\", cf.preperiod(), \"period =\", cf.period())\n",
        "\n",
        "prefix_rows, cycle = sqrt_states(13)\n",
        "print(table([(n+1, P, Q, a) for n, (P, Q, a) in enumerate(cycle)],\n",
        "            header_row=[\"n\", \"P_n\", \"Q_n\", \"a_n\"]))\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "id": "sage-08",
      "metadata": {},
      "source": [
        "**Prove the missing step.** A computer finding a cycle for seven\n",
        "examples does not prove Lagrange's theorem. Explain why the book's\n",
        "reduced complete quotients satisfy $0<P_n<\\sqrt D$ and\n",
        "$0<Q_n<2\\sqrt D$, and why integer states in this bounded region are\n",
        "finite. What argument shows that a general quadratic irrational\n",
        "eventually reaches that region?\n",
        "\n",
        "## 4. Galois's criterion: which tails repeat immediately?\n",
        "\n",
        "A quadratic irrational $x$ is **reduced** when $x>1$ and\n",
        "$-1<x'<0$. Galois's theorem says this is equivalent to pure\n",
        "periodicity. Use the nontrivial quadratic-field automorphism for $x'$;\n",
        "complex conjugation would leave these real numbers unchanged.\n"
      ]
    },
    {
      "cell_type": "code",
      "id": "sage-09",
      "metadata": {},
      "source": [
        "def conjugate_quadratic(x):\n",
        "    K = x.parent()\n",
        "    return K.hom([-K.gen()], K)(x)\n",
        "\n",
        "def is_reduced(x):\n",
        "    return AA(x) > 1 and -1 < AA(conjugate_quadratic(x)) < 0\n",
        "\n",
        "K2 = QuadraticField(2, 'r')\n",
        "r2 = K2.gen()\n",
        "K13 = QuadraticField(13, 's')\n",
        "s = K13.gen()\n",
        "examples = [r2, 1+r2, (1+r2)/2, -r2, (3+s)/2, s+3]\n",
        "for x in examples:\n",
        "    cf = continued_fraction(x)\n",
        "    pure = len(cf.preperiod()) == 0\n",
        "    assert pure == is_reduced(x)\n",
        "    print(\"x =\", x, \"x' =\", conjugate_quadratic(x),\n",
        "          \"prefix =\", cf.preperiod(), \"period =\", cf.period())\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "id": "sage-10",
      "metadata": {},
      "source": [
        "## 5. Reversing a period\n",
        "\n",
        "If $x=[\\overline{b_0,\\ldots,b_{L-1}}]$, then\n",
        "$-1/x'=[\\overline{b_{L-1},\\ldots,b_0}]$.\n",
        "Transposing a product of the symmetric digit matrices reverses their\n",
        "order. Construct both fixed points to check this exactly.\n"
      ]
    },
    {
      "cell_type": "code",
      "id": "sage-11",
      "metadata": {},
      "source": [
        "def periodic_root(word):\n",
        "    if not word or any(a < 1 for a in word):\n",
        "        raise ValueError(\"A purely periodic word has positive digits.\")\n",
        "    A, B, C, E = word_matrix(word).list()\n",
        "    delta = (E-A)^2 + 4*B*C\n",
        "    K = QuadraticField(delta, 's')\n",
        "    return (A-E+K.gen())/(2*C)\n",
        "\n",
        "word = [1, 2, 3]\n",
        "x = periodic_root(word)\n",
        "y = -1/conjugate_quadratic(x)\n",
        "assert word_matrix(word).transpose() == word_matrix(word[::-1])\n",
        "assert mobius(word_matrix(word[::-1]), y) == y\n",
        "assert continued_fraction(x).period() == tuple(word)\n",
        "assert continued_fraction(y).period() == tuple(word[::-1])\n",
        "print(\"Forward:\", continued_fraction(x))\n",
        "print(\"Reverse:\", continued_fraction(y))\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "id": "sage-12",
      "metadata": {},
      "source": [
        "**Explain.** Why is $-1/x'$ again reduced? Use the transpose identity\n",
        "and uniqueness of the positive fixed point to prove period reversal.\n",
        "In the next lab, applying this to $\\sqrt D+\\lfloor\\sqrt D\\rfloor$\n",
        "will explain the palindromic part of a square-root period.\n",
        "\n",
        "## 6. A small survey, and three proof tasks\n",
        "\n",
        "The following checks Galois's criterion across a family of surds.\n",
        "Extend the ranges only after explaining what the assertion says.\n"
      ]
    },
    {
      "cell_type": "code",
      "id": "sage-13",
      "metadata": {},
      "source": [
        "checked = 0\n",
        "for D in [2, 3, 5, 7, 13]:\n",
        "    K = QuadraticField(D, 'r')\n",
        "    for P in range(-3, 5):\n",
        "        for Q in range(1, 5):\n",
        "            x = (P+K.gen())/Q\n",
        "            assert is_reduced(x) == (continued_fraction(x).preperiod() == ())\n",
        "            checked += 1\n",
        "print(\"Exact Galois checks:\", checked)\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "id": "sage-14",
      "metadata": {},
      "source": [
        "1. Find two quadratic irrationals with the same periodic tail but\n",
        "   different prefixes. Display their conjugated period matrices.\n",
        "2. Recover the unique reduced predecessor: given reduced $x$, show\n",
        "   that $a=\\lfloor-1/x'\\rfloor$ and $a+1/x$ form that predecessor.\n",
        "   Explain why uniqueness makes eventual repetition pure.\n",
        "3. Prove that $\\sqrt D$ itself is never reduced, whereas\n",
        "   $\\sqrt D+\\lfloor\\sqrt D\\rfloor$ always is. Carefully distinguish\n",
        "   the first digit of the shifted surd from that of $\\sqrt D$.\n",
        "\n",
        "References: course Chapter 3; the [Sage continued-fraction reference](https://doc.sagemath.org/html/en/reference/diophantine_approximation/sage/rings/continued_fraction.html).\n"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "SageMath",
      "language": "sage",
      "name": "sagemath"
    },
    "language_info": {
      "name": "sage",
      "file_extension": ".sage",
      "mimetype": "text/x-sage"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 5
}