SNNN素因数定理

更新日：2022/9/30

以前の記事で，SNNN数列 $S_{10,7,3}$ が無数の素因数を含むことを証明した．この事実を一般化したものが，本記事で示すSNNN素因数定理である．この定理の証明はSNNN数論における一つの山場であり，これまでに証明した数々の定理を総動員するものである．本記事の内容を理解できれば，SNNN数論の中級者は卒業と言ってよいだろう．

SNNN素因数定理一般化SNNN数列 $S_{a,b,s}$ が $|a|>1,b\neq 0,D\neq 0$ を満たすならば，$S_{a,b,s}$ は無数の素因数を含む．

SNNN対数和

まず，SNNN素因数定理の証明において重要な役割を担うSNNN対数和を導入する．

定義全ての項が正であるような一般化SNNN数列 $S$ に対し，SNNN対数和 $\psi$ を $$ \psi(n) \coloneqq \sum_{i=0}^{n-1}\log{S(i)} $$ で定める．ただし，$\log$ は自然対数（底は $e$）．

例

SNNN数列 $S_{10,7,3}$ に対するSNNN対数和 $\psi$ を考えると $$ \begin{align*} \psi(0) &= 0 \\ \psi(1) &= \log{3} \\ \psi(2) &= \log{3} + \log{37} \\ \psi(3) &= \log{3} + \log{37} + \log{377}. \\ \end{align*} $$

SNNN対数和と素因数の関連性を見ておこう．まず，対数の基本性質として，次のような性質があった． $$ \log{377} = \log(13\cdot 29) = \log{13} + \log{29} $$ この式は次のようにも表される． $$ \log{377} = \nu_{13}(377) \cdot \log{13} + \nu_{29}(377) \cdot \log{29} $$ この式に，$377$ の素因数でない素数 $p$（すなわち $\nu_p(377)=0$ であるような $p$）を付け加えることも可能だろう． $$ \log{377} = \nu_{3}(377) \cdot \log{3} + \nu_{13}(377) \cdot \log{13} + \nu_{29}(377) \cdot \log{29} $$ 一般に，一般化SNNN数列 $S$ に現れる素因数の集合を $P_S$ とおけば $$ \log{S(i)} = \sum_{p\in P_S}\nu_p(S(i))\cdot \log{p} $$ であるから，SNNN対数和は $$ \begin{align*} \psi(n) &= \sum_{i=0}^{n-1}\sum_{p\in P_S}\nu_p(S(i))\cdot \log{p} \\ &= \sum_{p\in P_S} (\log{p}) \sum_{i=0}^{n-1} \nu_p(S(i)) \\ \end{align*} $$ と表される．ここで $$ \bar\psi_p(n) \coloneqq \sum_{i=0}^{n-1} \nu_p(S(i)) $$ とおけば $$ \begin{align} \psi(n) = \sum_{p\in P_S} \bar\psi_p(n)\cdot\log{p} \end{align} $$ が成り立つ．

ポイント SNNN対数和は，「一般化SNNN数列にわたる和」であると同時に「素因数にわたる和」でもある．

「都合の良い部分列」の選定

さて，以下ではSNNN対数和を用いてSNNN素因数定理の証明を行うのだが，与えられた一般化SNNN数列 $S=S_{a,b,s}$ の全ての項が正である保証はないため，そのままSNNN対数和を考えることはできない．そこで，$S$ の中から「都合の良い部分列」を取り出し，その中に素因数が無数に含まれていることを証明する方針をとる．

まず，$a\lt -1$ である場合を考える．このとき $S$ は「初項 $s$ に関数 $f(x)=ax+b$ を繰り返し適用した数列」である．ここで「初項 $s$ に関数 $f^2(x)=a^2x+(a+1)b$ を繰り返し適用した数列」$S'$ を考えると，$S'$ は一般化SNNN数列 $S_{a^2,(a+1)b,s}$ であり，なおかつ $S$ の部分列である．したがって，この $S'$ を新たに $S=S_{a,b,s}$ とおけば，一般性を失わずに $a\gt 1$ を仮定することができる．

いま，$a\gt 1$ であり，さらに定理の仮定より $D\neq 0$ であるから，$S$ は単調増加または単調減少のいずれかである（初回の演習問題を参照）．単調減少である場合には，全ての項を $-1$ 倍した一般化SNNN数列 $S_{a,-b,-s}$ を新たに $S=S_{a,b,s}$ とおくことで，一般性を失わずに $S$ が単調増加である（すなわち $D\gt 0$）と仮定する（これは元の数列の部分列ではないが，明らかに素因数の集合を保存している）．このとき，十分大きな自然数 $N$ をとれば，$S(N)$ 以降の項が全て正となる．この部分 $S_{a,b,S(N)}$ を新たに $S=S_{a,b,s}$ とおくことで，一般性を失わずに $S$ の全ての項が正であると仮定する．

なお，以上の一連の変換において，定理の仮定 $b\neq 0$ が保存されていることに注意しよう．

$\psi$ の下界

仮定 $a\gt 1$ と $s=S(0)\gt 0$ より $D=(a-1)s+b\gt b$ である．このことに注意し，一般化SNNN数列の一般項を用いて $S$ のSNNN対数和 $\psi$ を計算すると $$ \begin{align*} \psi(n) &= \sum_{i=0}^{n-1} \log{S(i)} \\ &= \sum_{i=0}^{n-1} \log\frac{Da^i-b}{a-1} \\ &= \sum_{i=0}^{n-1} \log\frac{Da^i}{a-1}\left(1-\frac{b}{Da^i}\right) \\ &= \sum_{i=0}^{n-1} \left\{ i\log a + \log\frac{D}{a-1} + \log\left(1-\frac{b}{Da^i}\right) \right\} \\ &= \frac{\log a}{2}n(n-1) + n\log\frac{D}{a-1} + \sum_{i=0}^{n-1}\log\left(1-\frac{b}{Da^i}\right) \\ &= \frac{\log a}{2}n^2 + \left(\log\frac{D}{\sqrt{a}(a-1)}\right)n + \sum_{i=0}^{n-1}\log\left(1-\frac{b}{Da^i}\right) \\ \end{align*} $$ となる．ここで不等式 $\log x\ge 1-\frac{1}{x}$ を用いると $$ \begin{align*} \sum_{i=0}^{n-1}\log\left(1-\frac{b}{Da^i}\right) &\ge \sum_{i=0}^{n-1}\left(1-\frac{Da^i}{Da^i-b}\right) \\ &= \sum_{i=0}^{n-1} \frac{-b}{Da^i-b} \\ &\ge -\frac{b}{Da^0-b} + \sum_{i=1}^{n-1} \frac{-\lvert b \rvert}{Da^i-Da^{i-1}} \\ &= -\frac{b}{D-b} - \frac{\lvert b\rvert}{D(a-1)}\sum_{i=1}^{n-1}\frac{1}{a^{i-1}} \\ &> -\frac{b}{D-b} - \frac{\lvert b\rvert}{D(a-1)}\sum_{i=1}^{\infty}\frac{1}{a^{i-1}} \\ &= -\frac{b}{D-b} - \frac{\lvert b\rvert}{D(a-1)}\frac{1}{1-a^{-1}} \\ &= -\frac{b}{D-b} - \frac{a\lvert b\rvert}{D(a-1)^2} \end{align*} $$ であるから $$ \begin{align} \psi(n) \gt \frac{\log a}{2}n^2 + \left(\log\frac{D}{\sqrt{a}(a-1)}\right)n - \frac{b}{D-b} - \frac{a\lvert b\rvert}{D(a-1)^2} \end{align} $$ を得る．とくに，右辺が $n$ の二次関数であることに着目しよう．

$\bar\psi_p$ の上界

続いて $\bar\psi_p(n)=\sum_{i=0}^{n-1} \nu_p(S(i))$ の上界を求めよう．$p$ が $a$ の素因数であるか否かで場合分けを行う．

$p \mid a$ の場合

仮定 $b\neq 0$ より，$\nu_p(S(n))$ は有界である（証明）．よってその上限を $M_p$ とおけば $$ \begin{align} \bar\psi_p(n) = \sum_{i=0}^{n-1} \nu_p(S(i)) \le \sum_{i=0}^{n-1} M_p = M_pn \end{align} $$ が成り立つ．

$p \nmid a$ の場合

$\bar\psi_p(n)$ について，実は次の関係式が成り立っている． $$ \begin{align*} \bar\psi_p(n) &= (\text{$S(0)$ から $S(n-1)$ までの $p$ の倍数の個数}) \\ &\,+ (\text{$S(0)$ から $S(n-1)$ までの $p^2$ の倍数の個数}) \\ &\,+ (\text{$S(0)$ から $S(n-1)$ までの $p^3$ の倍数の個数}) \\ &\,+ \cdots \\ \end{align*} $$ このことは，右辺の和において $p$ の倍数は1回，$p^2$ の倍数は（$p$ の倍数でもあるから）2回，$\cdots$ 数えられていることから理解される．

それでは，「$S(0)$ から $S(n-1)$ までの $p^k$ の倍数の個数」はどのように数えられるだろうか．我々は既に，素数冪の巡回定理および素数冪の巡回定理 (p=2)において，一般化SNNN数列 $S$ が $p^k$ を法とする基本周期 $$ \begin{align} u_{p^k}=\begin{cases} 1 & \text{if }k\le \nu_p(D)-\nu_p(a-1)+\nu_2(p) \\ p^{\max(0,k-\~k_p)}\cdot\ord_{p^{1+\nu_2(p)}}(a) & \text{otherwise} \\ \end{cases} \end{align} $$ を持つことを明らかにした（$\nu_2(p)$ を用いて一つの式にまとめている）．また，基本周期の性質は，$S$ 上の連続した $u_{p^k}$ 項に $p^k$ の倍数は高々1個しか存在しないことを主張する．このことから，$S(0)$ から $S(n-1)$ までの連続した $n$ 項には $p^k$ の倍数が高々 $\lceil\frac{n}{u_{p^k}}\rceil$ 個しか存在しないことが導かれる．ゆえに $$ \bar\psi_p(n) \le \sum_{k=1}^{\infty} \lceil\frac{n}{u_{p^k}}\rceil $$ と表せるが，この式は右辺の無限和が発散してしまい，使い物にならない．そこで，右辺の和を有限個で打ち切ることを考える．いま，$S$ は単調増加であるから，$S(0)$ から $S(n-1)$ までの全ての項は $S(n)$ 未満である．したがって，$p^k\ge S(n)$ すなわち $k\ge \log_p{S(n)}$ を満たすような $k$ については，$p^k$ の倍数が $S(n)$ より前に存在することはない．よって $$ \bar\psi_p(n) \le \sum_{k=1}^{\lfloor\log_p{S(n)}\rfloor} \lceil\frac{n}{u_{p^k}}\rceil $$ が成立する．

さて，この式の上界を与えるためには，$u_{p^k}$ の下界を調べればよい．(4)式において，常に $\nu_p(D)-\nu_p(a-1)+\nu_2(p)\le\~k_p$ であることに注意すれば $$ u_{p^k} \ge p^{k-\~k_p} $$ が得られる．したがって $$ \begin{align*} \bar\psi_p(n) &\le \sum_{k=1}^{\lfloor\log_p{S(n)}\rfloor} \lceil\frac{n}{u_{p^k}}\rceil \\ &\le \sum_{k=1}^{\lfloor\log_p{S(n)}\rfloor} \left(\frac{n}{u_{p^k}}+1\right) \\ &= \lfloor\log_p{S(n)}\rfloor + \sum_{k=1}^{\lfloor\log_p{S(n)}\rfloor} \frac{n}{u_{p^k}} \\ &\le \log_p{S(n)} + n\sum_{k=1}^{\lfloor\log_p{S(n)}\rfloor} \frac{1}{p^{k-\~k_p}} \\ &\lt \log_p{S(n)} + n\sum_{k=1}^\infty \frac{p^{\~k_p}}{p^k} \\ &= \log_p{S(n)} + \frac{p^{\~k_p}}{p-1}n \\ \end{align*} $$ が成り立つ．ここで $$ \begin{align*} \log_p{S(n)} &= \log_p\frac{Da^n-b}{a-1} \\ &\le \log_p\frac{Da^n+|b|}{a-1} \\ &\le \log_p\frac{Da^n+|b|a^n}{a-1} \\ &= \log_p\frac{D+|b|}{a-1}a^n \\ &= \log_p\frac{D+|b|}{a-1}+n\log_p{a} \\ \end{align*} $$ であるから $$ \begin{align} \bar\psi_p(n) \lt \left( \log_p{a}+\frac{p^{\~k_p}}{p-1} \right)n + \log_p\frac{D+|b|}{a-1} \end{align} $$ を得る．

(3),(5)式より，いずれの場合も $\bar\psi_p(n)$ は $n$ の一次関数で抑えられることが分かる．

証明の完結

ここで背理法を用いる．すなわち，$S$ に現れる素因数の集合 $P_S$ が有限集合であると仮定する．このとき(1)式に着目すると，$\psi(n)$ は $\bar\psi_p(n)$ の有限線形和である．$\bar\psi_p(n)$ が $n$ の一次関数で抑えられることから，それらの有限線形和である $\psi(n)$ もまた $n$ の一次関数で抑えられるはずである． $$ \psi(n) \le An+B $$ したがって特に $$ \lim_{n\to\infty}\frac{\psi(n)}{n^2} \le \lim_{n\to\infty}\frac{An+B}{n^2} =0 $$ である．一方，(2)式から $$ \lim_{n\to\infty}\frac{\psi(n)}{n^2}\ge \frac{\log{a}}{2} $$ が導かれ，矛盾が生じる．よって $P_S$ は無限集合である．

演習問題

一般化SNNN数列 $S_{1,b,s}$ （ただし $b\neq 0$ とする）は等差数列である．この数列はSNNN素因数定理の前提条件 $|a|>1$ を満たさないが，実は素因数を無数に含むことが知られている．このことを示そう．

一般化SNNN数列 $S_{2,b',s'}$ が $S_{1,b,s}$ の部分列となるような $(b',s')$ を1つ求めよ．
$s\neq 0$ ならば $S_{1,b,s}$ は無数の素因数を含むことを示せ．
前問の証明を $s=0$ の場合にも適用するにはどうすればよいか．

余談なお，演習問題(2)は誘導を無視して解くこともできる．フェルマーの小定理を用いて素数 $p$ で割り切れる項を直接構成する方法が自然であろう．あるいは，算術級数定理を認めれば上記の主張は自明である．