線形合同法とp進整数と縮小写像.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 線形合同法とp進整数と縮小写像"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$p$を素数，$e$を正整数，$a, b$を整数とする．\n",
    "$f: \\mathbb{Z}/p^e\\mathbb{Z} \\to \\mathbb{Z}/p^e\\mathbb{Z}$を\n",
    "$$f(x) = a x + b$$\n",
    "で定める．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">**命題1**\n",
    ">$a$が$p$の倍数であると仮定する．\n",
    ">このとき次が成立する．\n",
    ">\n",
    ">1. $f$の不動点，すなわち\n",
    ">$$f(x) = x$$\n",
    ">を満たす$x \\in \\mathbb{Z}/p^e\\mathbb{Z}$が存在する．\n",
    ">\n",
    ">2. $f$の不動点は一意である．\n",
    ">\n",
    ">3.  任意の$x_0 \\in \\mathbb{Z}/p^e\\mathbb{Z}$について次で定義される数列:\n",
    ">$$ x_n = f^n(x_0) $$\n",
    ">は不動点に収束する．（ここに$f^n$は$f$の$n$回合成）\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "証明．(1)と(2): \n",
    "$$ f(x) = x \\iff (a-1)x \\equiv -b \\pmod{p^e} $$\n",
    "だが，今$a$が$p$の倍数なので，$a-1$は$p$と互いに素．よってこの一次合同方程式には解が一意に存在する．\n",
    "\n",
    "(3): 数列の一般項は\n",
    "$$ x_n = a^n x_0 + (1 + a + a^2 + \\dots + a^{n-1})b $$\n",
    "となる．$a$が$p$の倍数なので$a^{n_0} \\equiv 0 \\pmod{p^e}$となる$n_0$がある．すると$n > n_0$なら\n",
    "$$ x_n = (1 + a + a^2 + \\dots + a^{{n_0}-1})b $$\n",
    "となって一定値をとる． ■"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "ところで次のようなよく知られた定理がある．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">**定理 (Banachの不動点定理)**\n",
    ">\n",
    ">$(X, d)$を完備距離空間，$f: X \\to X$を次を満たす写像とする: ある$k\\ (0 \\leq k < 1)$があって任意の$x, y \\in X$について\n",
    ">$$ d(f(x), f(y)) \\leq  k\\,d(x, y). $$\n",
    ">このとき$f$の不動点がただ一つ存在する．\n",
    ">また任意の$x_0$に対して数列$x_n = f^n(x_0)$は不動点に収束する．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Banachの不動点定理によって最初の命題を証明できないだろうか．$\\mathbb{Z}/p^e\\mathbb{Z}$には距離は離散距離しか入らないので使えそうにない．そこで$p$進整数環$\\mathbb{Z}_p$と呼ばれる空間を考える．\n",
    "\n",
    "$p$進整数環の定義はここではしないが，次のような性質を持つ．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $\\mathbb{Z}_p$には環構造が入る\n",
    "* $\\mathbb{Z} \\subset \\mathbb{Z}_p$である\n",
    "* $x \\in \\mathbb{Z}_p$に対して$x$の$p$進絶対値$|x|_p$が定まる\n",
    "* $|x|_p = 0 \\iff x = 0$\n",
    "* $|xy|_p = |x|_p |y|_p$\n",
    "* $|x + y|_p \\leq \\max\\{|x|_p, |y|_p\\}$\n",
    "* $x \\in \\mathbb{Z} \\setminus \\{0\\}$に対しては$x$を素因数分解したときの$p$の指数を$n$としたとき$|x|_p = p^{-n}$\n",
    "* $d(x, y) = |x - y|_p$と定めるとき$(\\mathbb{Z}_p, d)$は完備距離空間\n",
    "* 全射環準同型$\\varphi_e: \\mathbb{Z}_p \\to \\mathbb{Z}/p^e\\mathbb{Z}$があり，特に$x \\in \\mathbb{Z}$なら$\\varphi_e(x) = x \\bmod p^e$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$f$は$\\mathbb{Z}/p^e\\mathbb{Z}$上の写像であったが，これを$\\mathbb{Z}_p$上に修正したものを$\\tilde{f}$で表す:\n",
    "$$ \\tilde{f}: \\mathbb{Z}_p \\ni x \\mapsto (ax+b) \\in \\mathbb{Z}_p$$ \n",
    "\n",
    "この$\\tilde{f}$はBanachの定理の仮定を満たす．実際，\n",
    "\n",
    "\\begin{align*}\n",
    "d(\\tilde{f}(x), \\tilde{f}(y)) &= |(ax+b)-(ay+b)|_p \\\\\n",
    "&= |a(x-y)|_p \\\\\n",
    "&= |a|_p |x-y|_p \\\\\n",
    "&= |a|_p d(x, y)\n",
    "\\end{align*}\n",
    "\n",
    "であり，$a$が$p$の倍数だから$|a|_p < 1$である．\n",
    "\n",
    "よって$\\tilde{f}$の不動点$x$が存在し，それを$\\varphi_e$で移せば$f$の不動点を得る．ゆえに命題の(1)が示された．\n",
    "また，$\\mathbb{Z}/p^e\\mathbb{Z}$に離散位相を入れたとき，$\\varphi_e$が連続写像になるので，そこから命題の(3)を得る．\n",
    "(なお，残念ながら，命題の(2)はこの方法では示せない．)\n",
    "\n",
    "以上よりBanachの不動点定理によって最初の命題を(一部分を除いて)示せることがわかった．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$a = {\\rm 0x12344}$ (偶数なことに注意！), $b = {\\rm 0x6073}, p = 2, e = 20, x_0 = 1$としてみると次の表のようになる．下の桁から順に固定されていっている様子がわかる．\n",
    "\n",
    "| $n$  | $x_n$           |\n",
    "|------|-----------------|\n",
    "| $0$  | ${\\rm 0x00001}$ |\n",
    "| $1$  | ${\\rm 0x183b7}$ |\n",
    "| $2$  | ${\\rm 0x0620f}$ |\n",
    "| $3$  | ${\\rm 0x1796f}$ |\n",
    "| $4$  | ${\\rm 0xdceef}$ |\n",
    "| $5$  | ${\\rm 0x504ef}$ |\n",
    "| $6$  | ${\\rm 0x15cef}$ |\n",
    "| $7$  | ${\\rm 0x0bcef}$ |\n",
    "| $8$  | ${\\rm 0x63cef}$ |\n",
    "| $9$  | ${\\rm 0xc3cef}$ |\n",
    "| $10$ | ${\\rm 0x43cef}$ |\n",
    "| $11$ | ${\\rm 0x43cef}$ |\n",
    "| $12$ | ${\\rm 0x43cef}$ |"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}