SNNN予想と倍数法則・巡回定理
更新日：2022/9/30
SNNN予想
SNNN数論の歴史は，2014年に公開された1本の動画に遡る．この動画および関連文献にて提示された次の予想は，未だに証明・反証のいずれも成立しておらず，SNNN数論最大の未解決問題として残されている．
SNNN予想（siratama, 2014） SNNN素数（素数であるようなSNNN数）は無数に存在する．
前回の記事で定義した一般化SNNN数列を用いれば，この予想は「$S_{10,7,3}$ は，素数となる項を無数に含む」と言い換えられる（以下，表記を簡潔にするため，$S_{10,7,3}$ を単に $S$ と表記する）．
2022年9月時点で知られているSNNN素数は，$S(0), S(1), S(11), S(17), S(773)$ の5つである（出典はこちら）．このように，SNNN素数の出現は不規則であり，その所在を理論的に示すことは極めて困難である．そこで，まずはSNNN数が合成数となる十分条件を調べ，SNNN素数の候補を絞り込むことを考えよう．
SNNN数の倍数法則
SNNN数の素因数分解を以下に示す．これらの分解に何らかの法則性を見出せないだろうか． $$ \begin{align*} S(0) &= 3 & S(6) &= 3^2 \times 419753 \\ S(1) &= 37 & S(7) &= 37 \times 181 \times 5641 \\ S(2) &= 13 \times 29 & S(8) &= 13 \times 953 \times 30493 \\ S(3) &= 3 \times 1259 & S(9) &= 3 \times 1259259259 \\ S(4) &= 37 \times 1021 & S(10) &= 37 \times 19609 \times 52069 \\ S(5) &= 19 \times 59 \times 337 & S(11) &= 377777777777 \\ \end{align*} $$ 例えば，素因数 $3$ に着目すると，$3$ で割り切れるSNNN数は $S(0), S(3), S(6), S(9)$ であり，全て $S(3k)$ 型のSNNN数である（$k$ は自然数）．この観察から，次のような予想が立てられる．
- $S(3k)$ は $3$ で割り切れる．
実際，この予想は正しい．証明は省略するが，数学的帰納法によって容易に示すことができる．この法則により，$S(3k)$ は $3$ を除いて全て合成数であることが分かる．
実は，このような法則性は素因数 $3$ に限らず，あらゆる素因数 $p$ に対して存在することが知られている（倍数法則）．以下にその一例を示す．
- $S(3k+1)$ は $37$ で割り切れる．
- $S(6k+2)$ は $13$ で割り切れる．
- $S(18k+5)$ は $19$ で割り切れる．
素因数がこのように周期的に出現するのは何故だろうか．その本質は，SNNN数を素数 $p$ で割った余りを考えると分かりやすい．例えば，$p=3$ の場合を考えると，SNNN数列 $S$ の各項を $3$ で割った余りは $$ \begin{align} S\text{ mod }3=[0,1,2,0,1,2,0,1,2,\cdots] \end{align} $$ となっており，$0,1,2$ という長さ3のサイクルが繰り返されていることが分かる．このサイクルの長さを，$3$ を法とする $S$ の基本周期という．結局，SNNN数列の素因数分解における素因数 $p$ の出現周期とは，$p$ を法とするSNNN数列の基本周期に他ならない．
一般化SNNN数列の周期
(1)式の周期性を数式で表すことを考えよう．基本周期を $u(=3)$ とおけば，(1)式の周期性は $$ \begin{align*} S(0)\equiv S(0+u)\equiv S(0+2u)\equiv\cdots\equiv 0 & \\ S(1)\equiv S(1+u)\equiv S(1+2u)\equiv\cdots\equiv 1 &&\mod{3} \\ S(2)\equiv S(2+u)\equiv S(2+2u)\equiv\cdots\equiv 2 & \end{align*} $$ と表される．最右辺の値は周期性を論じる上では重要でないため無視すると，これらの式は $$ \begin{align} m\equiv n\mod{u} \implies S(m)\equiv S(n)\mod{3} \end{align} $$ と短くまとめられる．それでは，この式を基本周期の定義として採用してよいだろうか．実は，$u=3$ の他に $u=6$ や $u=9$ など，$u$ が基本周期の整数倍であれば(2)式を満たすことが分かる．結局，基本周期は「(2)式を満たす正整数 $u$ の中で最小のもの」として特徴付けられる．最小とは限らない一般の $u$ は単に周期と呼ぶことにしよう．
この考えを一般化し，周期および基本周期を次のように定義する（以下，記号 $S$ は $S_{10,7,3}$ に限らず一般の $S_{a,b,s}$ を表すものとする）．なお，前節では素数 $p$ を法とする周期のみを考えたが，ここでは一般の整数 $z$ を法とする．
定義 一般化SNNN数列 $S$ と整数 $z$ に対し，正整数 $u$ が $$ m\equiv n\mod{u} \implies S(m)\equiv S(n)\mod{z} $$ を満たすならば，$u$ は $z$ を法とする $S$ の周期であるという．
$z$ を法とする周期のうち最小のものを基本周期といい，$u_z$ で表す．
以下，一般化SNNN数の周期について，いくつかの事実を証明する．これらの性質は，関数 $f(x)=ax+b$ の基本性質 $$ m\equiv n\mod{z} \implies f(m)\equiv f(n)\mod{z} $$ によるものである．
次の補題は，一般化SNNN数列の周期を求めるうえで有用である．
補題 $S$ を一般化SNNN数列，$z$ を整数，$u$ を非負整数とする．このとき，次の2条件は同値である．
(1) $u$ は $z$ を法とする $S$ の周期
(2) $S(u) \equiv S(0)\mod{z}$
証明
(1)$\implies$(2) は周期の定義より明らか．(2)$\implies$(1) を示す．仮定は $f^u(s)\equiv s\mod{z}$ と表せる．いま，$m\equiv n\mod{u}$ なる $m,n\,(m\ge n)$ を考え，$m-n=qu$ とおく．このとき $S(m) \equiv f^m(s) \equiv f^{n+qu}(s) \equiv f^n(f^{qu}(s)) \equiv f^n((f^u)^q(s)) \equiv f^n(s) \equiv S(n)\mod{z}$．$\blacksquare$
この補題から，次の定理が導かれる．
定理 一般化SNNN数列 $S$ が $z$ を法とする基本周期 $u_z$ を持つならば $$ \begin{align} m\equiv n\mod{u_z} \iff S(m)\equiv S(n)\mod{z}. \end{align} $$
証明
$\implies$は明らか．$\impliedby$の対偶を示す．$m=Qu_z+m',n=qu_z+n'\,(0\le m',n'\lt u_z)$ とおき，一般性を失わずに $m'>n'$ を仮定する．以下，合同式の法を $z$ とする．このとき，$S(m)\equiv S(n)$ を仮定すると，周期性より $S(m')\equiv S(n')$ が成り立つから $$ \begin{align*} f^{m'}(s) &\equiv f^{n'}(s) \\ f^{u_z-n'}(f^{m'}(s)) &\equiv f^{u_z-n'}(f^{n'}(s)) \\ S(u_z+m'-n') &\equiv S(u_z) \\ S(m'-n') &\equiv S(0) \\ \end{align*} $$ となる．よって補題より $m'-n'$ は $S$ の周期であるが，これは $u_z$ の最小性に反する．したがって $S(m)\nequiv S(n)$．$\blacksquare$
余談 実は，(3)式は一般化SNNN数列の基本周期の同値な定義の一つである．すなわち，(3)式を仮定すれば「基本周期は最小の周期である」という命題を定理として導くことができる．SNNN数論の立場からは，(3)式を定義として採用する方が議論が簡明になるという利点がある．しかし，周期や基本周期といった概念は本来（一般化SNNN数列に限らず）一般の関数に対して定められるものであり，その際に(3)式が成立するとは限らない．他分野における同名の概念との不整合を避けるため，本サイトでは(3)式による定義を採用しないものとした．
一般化SNNN数列の基本周期 $u_p$ の計算
それでは，素数 $p$ を法とする一般化SNNN数列 $S$ の基本周期 $u_p$ を計算しよう．この節の合同式の法は全て素数 $p$ とする．補題より，一般化SNNN数列 $S$ の基本周期 $u_p$ は，合同方程式 $S(u)\equiv S(0)$ の最小の正の解である．さて，前回の記事で一般化SNNN数列の一般項を求めたが，これと全く同様にして合同式としての一般項 $$ S_{a,b,s}(n)\equiv\begin{cases} \frac{Da^n-b}{a-1} & \text{if }a\nequiv 1 \\ bn+s & \text{if }a\equiv 1 \end{cases} $$ が求められる．これを用いて方程式を解くと，以下のようになる．
$a\nequiv 1$ の場合
$$ \begin{align*} S(u) &\equiv S(0) \\ \frac{Da^u-b}{a-1} &\equiv s \\ Da^u-b &\equiv (a-1)s \\ Da^u-\{(a-1)s+b\} &\equiv 0 \\ Da^u-D &\equiv 0 \\ D(a^u-1) &\equiv 0 \\ \end{align*} $$ $D\equiv 0$ であれば任意の $u$ が解である．よって最小の正の解は $u_p=1$．$D\nequiv 0$ の場合は方程式 $a^u\equiv 1$ を解けばよい．ここで $a\nequiv 0$ であれば，正の解が必ず存在することが知られている（例えば，フェルマーの小定理 $a^{p-1}\equiv 1$ より解 $u=p-1$ を得る）．その中で最小のものを，$p$ を法とする $a$ の位数といい，$\ord_p(a)$ で表す．すなわち $u_p=\ord_p(a)$．一方，$a\equiv 0$ の場合に解が存在しないことは明らかである．
$a\equiv 1$ の場合
$$ \begin{align*} S(u) &\equiv S(0) \\ bu+s &\equiv s \\ bu &\equiv 0 \\ \end{align*} $$ $b\equiv 0$ であれば任意の $u$ が解である．よって最小の正の解は $u_p=1$．$b\nequiv 0$ の場合の解は $u\equiv 0$ すなわち $p$ の倍数全体であるから，最小の正の解は $u_p=p$．
注意 上の議論で「$xy\equiv 0$ ならば $x\equiv 0$ または $y\equiv 0$」という性質を用いているが，この性質は法が合成数でない場合に限って成立する．
以上の結果をまとめると，$a\nequiv 0\mod{p}$，すなわち $p$ が $a$ と互いに素であれば，$S$ は法 $p$ の基本周期 $u_p$ を持つことが分かる．以下，$p$ が $a$ と互いに素である場合のみを考える（そうでない場合については別途議論する）．このとき，基本周期 $u_p$ は $$ u_p=\begin{cases} 1 & \text{if ($a\nequiv 1$ and $D\equiv 0$) or ($a\equiv 1$ and $b\equiv 0$)} \\ p & \text{if $a\equiv 1$ and $D\nequiv 0$} \\ \ord_p(a) & \text{otherwise} \end{cases} $$ と表されるが，場合分けの条件式が長大であるため，これを簡略化したい．まず1行目の条件について，$a\equiv 1$ のとき $D=(a-1)s+b\equiv (1-1)s+b=b$ であることを用いて $$ \begin{align*} & \text{($a\nequiv 1$ and $D\equiv 0$) or ($a\equiv 1$ and $b\equiv 0$)} \\ \iff & \text{($a\nequiv 1$ and $D\equiv 0$) or ($a\equiv 1$ and $D\equiv 0$)} \\ \iff & D\equiv 0\mod{p} \\ \iff & p\mid D \end{align*} $$ と変形できる（最終行は「$p$ は $D$ の約数」の意）．2行目についても約数記号を用いて表記すれば，結局 $$ u_p=\begin{cases} 1 & \text{if }p\mid D \\ p & \text{if }p\nmid D\text{ and }p\mid a-1\\ \ord_p(a) & \text{otherwise} \\ \end{cases} $$ を得る．
巡回定理
本記事で示した基本周期の性質と $u_p$ の計算結果を合わせて巡回定理という．
巡回定理 $S_{a,b,s}$ を一般化SNNN数列，$p$ を $a$ と互いに素な素数とする．このとき， $$ m\equiv n\mod{u_p} \iff S_{a,b,s}(m)\equiv S_{a,b,s}(n)\mod{p}. $$ ただし $$ u_p=\begin{cases} 1 & \text{if }p\mid D \\ p & \text{if }p\nmid D\text{ and }p\mid a-1\\ \ord_p(a) & \text{otherwise}. \\ \end{cases} $$
例
SNNN数列 $S_{10,7,3}$ に巡回定理を適用すると，以下のような基本周期が得られる． $$ u_p=\begin{cases} 1 & \text{if }p=17 \\ 3 & \text{if }p=3\\ \ord_p(a) & \text{otherwise}. \\ \end{cases} $$ $p=3$ のとき $u_p=3$ となることは，本記事冒頭の観察と合致する．その他の場合，$u_p=1$ または $u_p=\ord_p(a)$ であるが，$\ord_p(a)$ は $p-1$ の約数であるという有名な事実を用いると，いずれの場合も $p-1$ が $u_p$ の倍数であることが導かれる．よって $p-1$ は法 $p$ の周期である．この事実はSNNNの補題として広く知られている（下記引用は本記事とは式の形が異なるが，同値な主張である）．
[SNNNの補題] (SNNN's lemma)
— siratama (@siratama_z) December 24, 2014
s(n)をn番目のSNNN数, pを7以上の素数とする時, 次が成り立つ.
s(n) ≡ s(n+p-1) mod p
ex) n=5, p=19の時, s(5) ≡ s(23) ≡ ... ≡ 0 mod 19
なお，巡回定理は後に，素数の累乗を法とする場合に対して一般化される（素数冪の巡回定理）．
