SNNN数の持ち上げ定理
Prerequisites (formal)
本記事内の命題は少々長めの前提を共通に持つ. ここでこの前提を定義し, 以下の命題すべてに対しこの前提を適用することを約束する.
$ \forall a, b, s\in\mathbb{Z}. $ \forall p\in\mathbb{P}. $ \forall k, i\in\mathbb{N}. $ \gcd(p, a) = 1\land 1\leq k\land a\ne 1.
SNNN数の巡回定理より$ p^kを法とした$ S_{a, b, s}の基本周期$ u_{p^k}\in\mathbb{N}\setminus\lbrace\,0\,\rbraceが存在する. 同様に$ p^{k+i}を法とした$ S_{a, b, s}の基本周期$ u_{p^{k+i}}\in\mathbb{N}\setminus\lbrace\,0\,\rbraceも存在する.
一般化SNNN数$ S_{a, b, s}に対し$ \tilde{k_p}を次のように定義する.
$ \tilde{k_p} := \begin{cases}v_p(D)-v_p(a-1)+W_p(a) & (p\ne 2)\cr v_2(D) & (p = 2\land a\equiv 1\pmod 4)\cr v_2(D)+v_2(a+1) & (p = 2\land a\equiv 3\pmod 4)\end{cases}
$ \mathrm{o}_G(x)を$ xの群$ Gにおける位数を表すものとして用いる. $ xから位数計算の対象となる群が一意に定まる場合, $ Gは省略される.
Statement (informal)
ある$ \alpha\in\mathbb{Z}について, $ S_{a, b, s}(n) \equiv \alpha \pmod {p^k}であるとする. $ \tilde{k_p}\leq kであるならば, これを$ {}\bmod {p^{k+i}}の合同式に持ち上げられる. つまり, ある$ m\in\mathbb{N}が存在して, $ S_{a, b, s}(m)\equiv S_{a, b, s}(n)\pmod {p^k}かつ$ S_{a, b, s}(m)\equiv \alpha\pmod {p^{k+i}}をみたす.
$ \forall n\in\mathbb{N}. $ \forall \alpha\in\mathbb{Z}. $ f\colon \mathbb{N}\ni j\mapsto n + ju_{p^k}\in\mathbb{N}. $ X := \lbrace\,j\mid j\in\mathbb{N}.\ 0\leq j\lt p^i.\,\rbrace. $ \pi\colon \mathbb{Z}\to \mathbb{Z}/p^{k+i}\mathbb{Z}は自然な全射. $ \tilde{k_p}\leq kであるとき以下が成立.
1. 二項関係$ \mathord{\sim} := \operatorname{Ker}(\pi\rvert _ {\mathbb{S}_{a, b, s}}\circ S_{a, b, s}\circ f)について, $ Xは$ \mathbb{N}/\mathord{\sim}の完全代表系. 特に$ \operatorname{Im}(\pi\rvert _ {\mathbb{S}_{a, b, s}}\circ S_{a, b, s}\circ f) = (\pi\rvert _ {\mathbb{S}_{a, b, s}}\circ S_{a, b, s}\circ f)(X).
2. $ \pi\rvert _ {\mathbb{S}_{a, b, s}}\circ S_{a, b, s}\circ f\rvert _ X\colon X\to \mathbb{Z}/p^{k+i}\mathbb{Z}は単射.
3. $ \exists j\in\mathbb{N}. $ \tilde{k_p}\leq k\land S_{a, b, s}(n)\equiv \alpha\pmod {p^k}\implies S_{a, b, s}(f(j))\equiv \alpha\pmod {p^{k+i}}.
4. $ \exists j\in\mathbb{N}. $ \tilde{k_p}\leq k\land p^{\tilde{k_p}}\mid S_{a, b, s}(n)\implies p^k\mid S_{a, b, s}(f(j)).
Proof
以降$ \varphi := \pi\rvert _ {\mathbb{S}_{a, b, s}}\circ S_{a, b, s}\circ f\rvert _ Xとする.
1.
SNNN数の周期 Thm. 1より$ \forall j_1, j_2\in\mathbb{N}. $ \begin{aligned}j_1 \sim j_2&\iff S_{a, b, s}(f(j_1))\equiv S_{a, b, s}(f(j_2))\pmod {p^{k+i}}\cr &\iff f(j_1) \equiv f(j_2)\pmod {u_{p^{k+i}}}\cr &\iff f(j_1) - f(j_2)\equiv (j_1 - j_2)u_{p^k}\equiv 0\pmod {u_{p^{k+i}}}\end{aligned}
Lem. Aより$ u_{p^{k+i}} = p^iu_{p^k}.
$ u_{p^k}\mid u_{p^{k+i}}より$ u_{p^k}は$ \mathbb{Z}/u_{p^{k+i}}\mathbb{Z}における零因子.
$ pは素数だから$ \forall x\in\mathbb{N}. $ \exists t\in\mathbb{N}. $ xu_{p^k} \equiv 0 \pmod {u_{p^{k+i}}} \iff p^i\mid x.
よって$ p^i\mid (j_1 - j_2) \iff (j_1 - j_2)u_{p^k}\equiv 0\pmod {u_{p^{k+i}}}.
上述の式と合わせ, $ j_1 \equiv j_2\pmod {p^i}\iff j_1\sim j_2を得る.
$ \forall m\in\mathbb{N}. $ m\sim (m\bmod p^i).
ここで$ \forall x\in X. $ 0\leq x\lt p^i. より$ \forall x, y\in X. $ x = y\iff x\equiv y\pmod {p^i}\iff x \sim y. であるから, $ Xは$ \mathbb{N} / \mathord{\sim}の完全代表系.
2. (1.)より$ Xは $ \mathbb{N}/\mathord{\sim}の完全代表系であるから, $ \forall j_1, j_2\in X. $ j_1\ne j_2 \implies \varphi(j_1)\ne \varphi(j_2). 即ち単射.
3.
$ \forall j\in X. $ \exists! t\in\mathbb{Z}. $ S_{a, b, s}(f(j))\bmod p^{k+i} = (S_{a, b, s}(f(j))\bmod p^k) + tp^k.
$ S_{a, b, s}(f(j))\bmod p^k = S_{a, b, s}(n)\bmod p^kより以降これに置き換えて記す
$ 0\leq S_{a, b, s}(f(j))\bmod p^{k+i}\lt p^{k+i}より$ 0\leq tp^k\lt p^{k+i}であるから$ 0\leq t\lt p^i.
よって$ ((S_{a, b, s}(f(j))\bmod p^{k+i}) - (S_{a, b, s}(n)\bmod p^k) / p^k = t\in X.
簡単のため, $ g\colon X\ni j\mapsto t\in Xとおく.
(2.)より$ \varphiは単射だから$ \forall j_1, j_2\in X. $ j_1\ne j_2\implies \varphi(j_1)\ne \varphi(j_2).
$ S_{a, b, s}(f(j_1))\bmod p^{k+i} \ne S_{a, b, s}(f(j_2))\bmod p^{k+i}なので$ g(j_1) \ne g(j_2).
よって$ gは単射. 特に$ g\colon X\to Xかつ$ Xは有限集合なので全単射.
ここで$ \exists! t\in\mathbb{Z}. $ \alpha\bmod p^{k+i} = (\alpha\bmod p^k) + tp^k.
$ \alpha\equiv S_{a, b, s}(n)\pmod {p^k}より$ \alpha\bmod p^{k+i} = (S_{a, b, s}(n)\bmod p^k) + tp^k.
$ 0\leq \alpha\bmod p^{k+i}\lt p^{k+i}より$ 0\leq tp^k\lt p^{k+i}であるから$ 0\leq t\lt p^i.
よって$ ((\alpha\bmod p^{k+i}) - (S_{a, b, s}(n)\bmod p^k)) / p^k = t\in X.
$ j := g^{-1}(t)とする.
$ g(j) = ((S_{a, b, s}(f(j))\bmod p^{k+i}) - (S_{a, b, s}(n)\bmod p^k)) / p^k = tである.
他方$ S_{a, b, s}(f(j))\bmod p^{k+i} = S_{a, b, s}(n)\bmod p^k + tp^k = \alpha\bmod p^{k+i}.
したがって$ S_{a, b, s}(f(j))\equiv \alpha\pmod {p^{k+i}}.
4.
$ \ell := k - \tilde{k_p}とおく. 前提より$ 0\leq \ellかつ$ \tilde{k_p} + \ell = k.
$ S_{a, b, s}(n)\equiv 0\pmod {p^{\tilde{k_p}}}であるから, (3.)より$ \exists j\in\mathbb{N}. $ S_{a, b, s}(f(j))\equiv 0\pmod {p^{\tilde{k_p}+\ell}}. $ \Box
Lem. A (formal)
$ \tilde{k_p}\leq k \implies u_{p^{k+i}} = p^iu_{p^k}.
Proof
$ p \ne 2のとき
$ \begin{aligned}\tilde{k_p} - (v_p(D) - v_p(a-1) + v_2(p)) &= v_p(D)-v_p(a-1)+W_p(a) - v_p(D) + v_p(a-1) - 0\cr &= W_p(a)\cr&\geq 1.\end{aligned}
$ p = 2かつ$ a\equiv 1\pmod 4のとき
$ \begin{aligned}\tilde{k_p} - (v_p(D) - v_p(a-1) + v_2(p)) &= v_2(D) - v_2(D) + v_2(a-1) - 1\cr&= v_2(a-1) - 1\cr &\geq 2 - 1\cr& = 1. \end{aligned}
$ p = 2かつ$ a\equiv 3\pmod 4のとき
$ \begin{aligned}\tilde{k_p} - (v_p(D) - v_p(a-1) + v_2(p)) &= v_2(D) - v_2(D)+v_2(a+1)\cr &= v_2(a+1)\cr &\geq 2. \end{aligned}
いずれの場合も$ v_p(D) - v_p(a-1) + v_2(p)\lt \tilde{k_p}\leq kだから$ u_{p^k} = p^{k - \tilde{k_p}}\mathrm{o}_{(\mathbb{Z}/p^t\mathbb{Z})^\times}(a).
$ 0\leq iより$ u_{p^{k+i}} = p^{k + i - \tilde{k_p}}\mathrm{o}_{(\mathbb{Z}/p^t\mathbb{Z})^\times}(a) = p^i(p^{k - \tilde{k_p}}\mathrm{o}_{(\mathbb{Z}/p^t\mathbb{Z})^\times}(a)) = p^iu_{p^k}. $ \Box
Note
計算量の観点からは$ i = 1の場合のみを利用するほうがよい
$ \lvert X\rvert = p^i, かつ$ g^{-1}の計算にその全探索が必要
$ \forall j\in\mathbb{N}. $ 0\leq j\lt iについて, $ p^kから$ p^{k+i-j}への持ち上げを実施する際の探索空間は$ \lvert X\rvert = p^{i-j}であり, 時間計算量は$ O(p^{i - j})
残る$ j回を追加探索することを鑑みて, $ p^kから$ p^{k+i}への持ち上げ計算量は$ O(p^{i-j} + p^{j})である
$ j = 1とおき, $ p^{i - j}を再度分割した場合, 同様の議論を繰り返せる
最終的な計算量は$ O(p\cdot i).
指数部が最も小さいという点でこれが計算量として最小