SNNN素因数の無限性定理
記号として SNNN対数和における$ \mathcal{L}_{a, b, s}等を利用する. Statement (formal)
$ \forall a, b, s\in\mathbb{Z}. $ X_{a, b, s} := \lbrace\,p\mid p\in\mathbb{P}.\ \exists x\in\mathbb{S}_{a, b, s}.\ p\mid x.\,\rbrace. $ \lvert a\rvert \gt 1\land b\ne 0\land D\ne 0\implies \forall n\in\mathbb{N}.\ n\lt \lvert X_{a, b, s}\rvert.
Proof
一般化SNNN数の全体からなる集合 Prop. 2, Prop. 3より, $ \exists a', b', s'\in\mathbb{Z}. $ 0\lt a\land\mathbb{S}_{a', b', s'}\subseteq\mathbb{N}\setminus\lbrace\,0\,\rbrace\land X_{a', b', s'}\subseteq X_{a, b, s}. $ \lvert X_{a', b', s'}\rvert\leq \lvert X_{a, b, s}\rvertより$ X_{a', b', s'}について示せば十分である
以降$ 1\lt aかつ$ \mathbb{S}_{a, b, s}\subseteq\mathbb{N}\setminus\lbrace\,\,0\,\rbraceを仮定する
いま$ \exists n\in\mathbb{N}. $ \lvert X_{a, b, s}\rvert = r. を仮定する.
有限集合であるから$ X_{a, b, s} = \lbrace\,p_0, p_1, \ldots, p_{r-1}\,\rbraceと添字付けられる. なお添字付けの順序に以降の議論は依存しない.
SNNN対数和 Prop. 2より $ \mathcal{L}_{a, b, s}(n) = \sum_{p\in\mathbb{P}} \mathcal{L}_{a, b, s}^{(p)}(n) = \sum_{i = 0} ^ {r - 1} \mathcal{L}_{a, b, s}^{(p_i)}(n)である Lem. 2より$ \sum_{i = 0} ^ {r - 1} \mathcal{L}_{a, b, s}^{(p_i)}(n) = \sum_{i = 0} ^ {r - 1} O(n) = O(n)である.
$ \exists k\in\mathbb{N}\setminus\lbrace\,0\,\rbrace. $ \exists n_0\in\mathbb{N}. $ \forall n\in\mathbb{N}. $ n_0\lt n\implies \sum_{i = 0} ^ {r - 1} \mathcal{L}_{a, b, s}^{(p_i)}(n) = \mathcal{L}_{a, b, s}(n) \leq kn.
ところがLem. 1より$ \mathcal{L}_{a, b, s}(n) = \Omega(n^2)である.
$ \exists \ell\in\mathbb{N}\setminus\lbrace\,0\,\rbrace. $ \exists n_1\in\mathbb{N}. $ \forall n\in\mathbb{N}. $ n_1\lt n\implies \mathcal{L}_{a, b, s}(n) \geq \ell n^2.
$ \max(n_0, n_1)\lt n\implies \mathcal{L}_{a, b, s}(n) \geq \ell n^2 \land \mathcal{L}_{a, b, s}(n) \leq k n である
$ \mathcal{L}_{a, b, s}(n) \geq \ell n^2 \land \mathcal{L}_{a, b, s}(n) \leq k n\implies 0\leq kn - \ell n^2より$ \max(n_0, n_1, k/\ell + 1)\leq n\implies 0\leq kn - \ell n^2.
ところが$ k(k/\ell+1) - \ell(k/\ell+1)^2 = k^2/\ell + k - (k^2/\ell + 2k + \ell) = -(k+\ell)\lt 0であり矛盾
背理法により, $ X_{a, b, s}は無限集合. $ \Box
Lem. 1 (formal)
$ \forall a, b, s\in\mathbb{Z}. $ \forall n\in\mathbb{N}. $ a\lt 1\land b\ne 0\land \mathbb{S}_{a, b, s}\subseteq \mathbb{N}\setminus\lbrace\,0\,\rbrace\implies \mathcal{L}_{a, b, s}(n) = \Omega(n^2). ただし$ \Omegaはランダウの記号.
Proof
まず以下が成り立つ.
$ \begin{aligned} \mathcal{L}_{a, b, s}(n) &= \sum_{i=0}^{n-1} \log(S_{a, b, s}(S(i)))\cr&= \sum_{i=0}^{n-1} \log\left(\frac{a^iD-b}{a-1}\right)\cr&= \sum_{i=0}^{n-1}\log\left(\frac{a^iD}{a-1}\left(1- \frac{b}{a^iD}\right)\right)\cr&= \sum_{i=0}^{n-1}\log\left(\frac{a^iD}{a-1}\right) + \log\left(1 - \frac{b}{a^iD}\right)\cr&= \sum_{i=0}^{n-1}i\log(a)+(\log(D)-\log(a-1)) + \log\left(1 - \frac{b}{a^iD}\right)\cr&= \frac{n(n-1)}{2}\log(a)+n(\log(D)-\log(a-1)) + \sum_{i=0}^{n-1}\log\left(1 - \frac{b}{a^iD}\right)\cr&= \frac{\log(a)}{2}n^2 + \left(\log(D)-(\log(a^{1/2})+\log(a-1))\right)n + \sum_{i=0}^{n-1}\log\left(1 - \frac{b}{a^iD}\right)\cr&= \frac{\log(a)}{2}n^2 + \log\left(\frac{D}{\sqrt{a}(a-1)}\right)n + \sum_{i=0}^{n-1}\log\left(1 - \frac{b}{a^iD}\right)\end{aligned}
次に$ a\gt 1, s = S_{a, b, s}(0)\in\mathbb{N}より$ D = (a-1)s + b \gt b. $ \forall i\in\mathbb{N}. $ 0\lt i \implies a\lt a^i. であるから$ \forall i\in\mathbb{N}. $ D\gt b \iff a^iD\geq D\gt b\iff 1\gt \frac{b}{a^iD} \iff 1 - \frac{b}{a^iD} \gt 0.
したがって
$ \begin{aligned}\sum_{i=0}^{n-1}\log\left(1 - \frac{b}{a^iD}\right)&\gt \sum_{i=0}^{n-1}\left(1 - \frac{1}{1 - \frac{b}{a^iD}}\right)\cr &= \sum_{i=0}^{n-1}\left(1 - \frac{a^iD}{a^iD - b}\right)\cr&= \sum_{i=0}^{n-1}\frac{-b}{a^iD - b}\cr&=\frac{-b}{D - b} + \sum_{i=1}^{n-1}\frac{-b}{a^iD - b}\cr&\geq -\frac{b}{D - b} - \sum_{i=1}^{n-1}\frac{\lvert b\rvert}{a^iD - b}\cr\end{aligned}
このとき$ a\gt 1\land D\gt bより$ \forall i\in\mathbb{N}\setminus\lbrace\,0\,\rbrace. $ a^iD - b \gt a^iD - a^{i-1}D\iff \frac{\lvert b\rvert}{a^iD - b} \lt \frac{\lvert b\rvert}{a^iD - a^{i-1}D}なので
$ \begin{aligned}\sum_{i=0}^{n-1}\log\left(1 - \frac{b}{a^iD}\right)&\gt -\frac{b}{D - b} - \sum_{i=1}^{n-1}\frac{\lvert b\rvert}{a^iD - b}\cr&\gt -\frac{b}{D - b} - \sum_{i=1}^{n-1}\frac{\lvert b\rvert}{a^iD - a^{i-1}D}\cr&= -\frac{b}{D - b} - \frac{\lvert b\rvert}{D(a - 1)}\sum_{i=1}^{n-1}\frac{1}{a^{i-1}}\cr&\gt -\frac{b}{D - b} - \frac{\lvert b\rvert}{D(a - 1)}\sum_{i=0}^{n-1}\frac{1}{a^{i}}\cr&= -\frac{b}{D - b} - \frac{\lvert b\rvert}{D(a - 1)}\frac{1 - a^{-n}}{1 - a^{-1}}\cr&= -\frac{b}{D - b} - \frac{a\lvert b\rvert(1 - a^{-n})}{D(a - 1)^2}\cr&\gt -\frac{b}{D - b} - \frac{a\lvert b\rvert}{D(a - 1)^2}\end{aligned}
合わせて$ \mathcal{L}_{a, b, s}(n) \gt \frac{\log(a)}{2}n^2 + \log\left(\frac{D}{\sqrt{a}(a-1)}\right)n - \left(\frac{b}{D - b} + \frac{a\lvert b\rvert}{D(a - 1)^2}\right).
$ B := \log\left(\frac{D}{\sqrt{a}(a-1)}\right).
$ C := -\left(\frac{b}{D - b} + \frac{a\lvert b\rvert}{D(a - 1)^2}\right).
$ a\ne 0, $ b\ne 0より$ B\gt 0.
$ k := \log(a)/2, $ n_0 := -C/Bとおくと, $ \forall n\in\mathbb{N}. $ n_0\lt nならば$ \mathcal{L}_{a, b, s}(n) - kn^2 = Bn + C \gt Bn_0+C = 0である.
よって$ \mathcal{L}_{a, b, s}(n) = \Omega(n^2). $ \Box
Lem. 2 (formal)
$ \forall a, b, s\in\mathbb{Z}. $ \forall n\in\mathbb{N}. $ \forall p\in\mathbb{P}. $ a\gt 1\land b\ne 0\land \mathbb{S}_{a, b, s}\subseteq \mathbb{N}\setminus\lbrace\,0\,\rbrace\implies \mathcal{L}_{a, b, s}^{(p)}(n) = O(n). ただし$ Oはランダウの記号.
Proof
$ a\mid pのとき
一般化SNNN数列のp進付値 Thm. 2 (2.)よりある$ M\in\mathbb{N}が存在して$ \forall n\in\mathbb{N}. $ v_p(S_{a, b, s}(n))\leq M. したがって$ \mathcal{L}_{a, b, s}^{(p)}(n) = \log(p)\sum_{i=0}^{n-1}v_p(S_{a, b, s}(i))\leq \log(p)\sum_{i=0}^{n-1} M = \log(p)Mn より $ \mathcal{L}_{a, b, s}^{(p)}(n) = O(n).
$ a\nmid pのとき
$ \forall n, k\in\mathbb{N}. $ n\ne 0とする
以下の通り記号$ \delta(n, k), $ \mathcal{F}_p(k), $ \mathcal{G}_p(n)を定義する.
$ \delta(k, n) := \begin{cases}1 & (p^k\mid S_{a, b, s}(n))\cr 0 & (p^k\nmid S_{a, b , s}(n)).\end{cases}
$ \mathcal{F}_p(k, n) := \lbrace\, i\mid i\in\mathbb{N}.\ 0\leq i\lt n\land p^k\mid S_{a, b, s}(i).\ \,\rbrace.
$ \mathcal{G} _ p(k, n) := \lbrace\,\ell\mid \ell\in\mathbb{N}.\ 0\lt \ell\leq k\land p^\ell\mid S_{a, b, s}(n)\,\rbrace.
すると直接以下が従う
$ \forall i\in\mathbb{N}. $ i\in\mathcal{F}_p(k, n) \iff \delta(k, i) = 1.
$ i\in\mathcal{F}_p(k, n) \iff p^k\mid S_{a, b, s}(i) \iff \delta(k, i) = 1.
$ \forall \ell\in\mathbb{N}. $ \ell\in\mathcal{G}_p(k, n) \iff \delta(\ell, n) = 1.
$ \ell\in\mathcal{G}_p(k, n)\iff p^\ell\mid S_{a, b, s}(n)\iff \delta(\ell, n) = 1.
$ \forall \ell\in\mathbb{N}. $ \ell\in\mathcal{G}_p(k, n)\iff \ell\leq v_p(S_{a, b, s}(n)).
$ \forall i, j\in\mathcal{F}_p(k, n). $ i\lt j \implies j - i\geq u_{p^k}. ただし$ u_{p^k}は法$ p^kにおける$ S_{a, b, s}の基本周期.
SNNN数の巡回定理 Cor. 3より $ u_{p^k} = \begin{cases}1 & (k\leq v_p(D) - v_p(a-1) + v_2(p))\cr p^{\max(0, k-\tilde{k_p})}\mathrm{o}_{(\mathbb{Z}/p^t\mathbb{Z})^\times}(a) & (\text{otherwise})\end{cases} $ u_{p^k}は基本周期であるから, $ \forall i, j\in\mathbb{N}. $ i\lt jのとき$ j - i\lt u_{p^k}\implies S_{a, b, s}(i)\not\equiv S_{a, b, s}(j)\pmod {p^k}.
このため$ S_{a, b, s}(i)\equiv S_{a, b, s}(j)\pmod {p^k} \implies j - i\geq u_{p^k}.
よって次が成立
$ \lvert \mathcal{F}_p(k, n)\rvert = \sum_{i = 0}^{n-1} \delta(k, i).
$ \lvert \mathcal{G}_p(k, n)\rvert = \sum_{\ell = 1}^{k} \delta(\ell, n).
$ \sum_{\ell=1}^{k}\lvert \mathcal{F}_p(\ell, n)\rvert = \sum_{i = 0}^{n - 1}\lvert\mathcal{G}_p(k, i)\rvert.
$ \begin{aligned}\sum_{\ell=1}^{k}\lvert \mathcal{F}_p(\ell, n)\rvert &= \sum_{\ell=1}^{k}\left(\sum_{i = 0}^{n-1} \delta(\ell, i)\right)\cr&= \sum_{i = 0}^{n-1}\left(\sum_{\ell=1}^{k}\delta(\ell, i)\right)\cr &= \sum_{i = 0}^{n - 1}\lvert\mathcal{G}_p(k, i)\rvert.\end{aligned}
$ \lvert\mathcal{G}_p(k, n)\rvert = \min(v_p(S_{a, b, s}(n)), k).
特に$ k = \lceil\log_p(S_{a, b, s}(n))\rceilであるとき$ p^k\geq S_{a, b, s}(n)であるから$ \lvert\mathcal{G}_p(\lceil\log_p(S_{a, b, s}(n))\rceil, n)\rvert = \min(v_p(S_{a, b, s}(n)), \lceil\log_p(S_{a, b, s}(n))\rceil) = v_p(S_{a, b, s}(n)).
$ \lvert \mathcal{F}_p(k, n)\rvert \leq \left\lfloor\frac{n}{u_{p^k}}\right\rfloor + 1.
$ \forall i, j\in\mathcal{F}_p(k, n). $ i\lt j \implies j - i\geq u_{p^k}. より$ p^k\mid S_{a, b, s}(0)\land \left\lfloor\frac{n}{u_{p^k}}\right\rfloor u_{p^k}\lt nのとき$ \mathcal{F}_p(k, n) = \left\lbrace\,0, u_{p^k}, 2u_{p^k}, \ldots, \left\lfloor\frac{n}{u_{p^k}}\right\rfloor u_{p^k}\,\right\rbrace = \left\lbrace\,iu_{p^k}\mid i\in\mathbb{N}.\ i\lt \left\lfloor\frac{n}{u_{p^k}}\right\rfloor+1\,\right\rbraceであり, 特にこれが最大である.
この場合$ \lvert\mathcal{F}_p(k, n)\rvert = \left\lfloor\frac{n}{u_{p^k}}\right\rfloor + 1である.
ここまでの結果と$ \forall i, n\in\mathbb{N}. $ i\lt n\implies S_{a, b, s}(i)\lt S_{a, b, s}(n)から以下が成り立つ.
$ \begin{aligned}\mathcal{L}_{a, b, s}^{(p)}(n) &= \log(p)\sum_{i = 0}^{n - 1} v_p(S_{a, b, s}(i))\cr &= \log(p)\sum_{i=0}^{n-1}\left\lvert\mathcal{G}_p\left(\left\lceil\log_p(S_{a, b, s}(i))\right\rceil, i\right)\right\rvert\cr&=\log(p)\sum_{i=0}^{n-1}\left\lvert\mathcal{G}_p\left(\left\lceil\log_p(S_{a, b, s}(n))\right\rceil, i\right)\right\rvert\cr&=\log(p)\sum_{\ell=1}^{\left\lceil\log_p(S_{a, b, s}(n))\right\rceil}\left\lvert\mathcal{F}_p\left(\ell, n\right)\right\rvert\cr&\leq\log(p)\sum_{\ell=1}^{\left\lceil\log_p(S_{a, b, s}(n))\right\rceil}\left(\left\lfloor\frac{n}{u_{p^\ell}}\right\rfloor + 1\right)\cr&= \log(p)\left(\left\lceil\log_p(S_{a, b, s}(n))\right\rceil+\sum_{\ell=1}^{\left\lceil\log_p(S_{a, b, s}(n))\right\rceil}\left\lfloor\frac{n}{u_{p^\ell}}\right\rfloor\right)\cr\end{aligned}
いま$ v_p(D) - v_p(a-1) + v_2(p) \leq \tilde{k_p}であるから$ \forall k\in\mathbb{N}. $ 1\leq k\implies u_{p^k}\geq p^{k - \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}
$ p\ne 0のとき
$ \tilde{k_p} - v_p(D) + v_p(a-1) - 0 = W_p(a)\geq 0より成立.
$ p = 2かつ$ p\equiv 1\pmod 4のとき
$ \tilde{k_p} - v_p(D) + v_p(a-1) - 1 = v_p(a-1)-1\geq 2 - 1 \geq 0より成立.
$ p = 2かつ$ p \equiv 3\pmod 4のとき:
$ \tilde{k_p} - v_p(D) + v_p(a - 1) - 1 = v_2(a + 1) + v_p(a - 1) - 1\geq 1 + 2 - 1\geq 0より成立.
$ u_{p^k} = 1のとき
$ k\leq v_p(D) - v_p(a - 1) + v_2(p)より$ k - \tilde{k_p}\leq v_p(D) - v_p(a - 1) + v_2(p) - \tilde{k_p}\leq 0.
$ 0\lt p^{k - \tilde{k_p}}\leq 1より成立.
$ u_{p^k} \ne 1のとき
$ u_{p^k} = p^{\max(0, k-\tilde{k_p})}\mathrm{o}_{(\mathbb{Z}/p^t\mathbb{Z})^\times}(a)\geq p^{\max(0, k-\tilde{k_p})} \geq p^{k-\tilde{k_p}}.
よって以下が成立
$ \begin{aligned}\mathcal{L}_{a, b, s}^{(p)}(n) &\leq \log(p)\left(\left\lceil\log_p(S_{a, b, s}(n))\right\rceil+\sum_{\ell=1}^{\left\lceil\log_p(S_{a, b, s}(n))\right\rceil}\left\lfloor\frac{n}{u_{p^\ell}}\right\rfloor\right)\cr&\leq \log(p)\left(\left\lceil\log_p(S_{a, b, s}(n))\right\rceil+\sum_{\ell=1}^{\left\lceil\log_p(S_{a, b, s}(n))\right\rceil}\frac{n}{u_{p^\ell}}\right)\cr&= \log(p)\left(\left\lceil\log_p(S_{a, b, s}(n))\right\rceil+n\sum_{\ell=1}^{\left\lceil\log_p(S_{a, b, s}(n))\right\rceil}\frac{1}{u_{p^\ell}}\right)\cr&\leq \log(p)\left(\left\lceil\log_p(S_{a, b, s}(n))\right\rceil+n\sum_{\ell=1}^{\left\lceil\log_p(S_{a, b, s}(n))\right\rceil}\frac{1}{p^{\ell-\tilde{k_p}}}\right)\cr&\leq \log(p)\left(\left\lceil\log_p(S_{a, b, s}(n))\right\rceil+np^{\tilde{k_p}}\sum_{\ell=1}^{\left\lceil\log_p(S_{a, b, s}(n))\right\rceil}\frac{1}{p^{\ell}}\right)\cr&\lt \log(p)\left(\left\lceil\log_p(S_{a, b, s}(n))\right\rceil+np^{\tilde{k_p}}\sum_{\ell=1}^{\left\lceil\log_p(S_{a, b, s}(n))\right\rceil+1}\frac{1}{p^{\ell}}\right)\cr&= \log(p)\left(\left\lceil\log_p(S_{a, b, s}(n))\right\rceil+np^{\tilde{k_p}}\left(\frac{1 - p^{-\left\lceil\log_p(S_{a, b, s}(n))\right\rceil}}{1 - p^{-1}} - 1\right)\right)\cr\end{aligned}
続いて以下も成立.
$ \begin{aligned}\mathcal{L}_{a, b, s}^{(p)}(n) &\lt \log(p)\left(\left\lceil\log_p(S_{a, b, s}(n))\right\rceil+np^{\tilde{k_p}}\left(\frac{1 - p^{-\left\lceil\log_p(S_{a, b, s}(n))\right\rceil}}{1 - p^{-1}} - 1\right)\right)\cr&\leq \log(p)\left(\left\lceil\log_p(S_{a, b, s}(n))\right\rceil+np^{\tilde{k_p}}\left(\frac{1}{1 - p^{-1}} - 1\right)\right)\cr&= \log(p)\left(\left\lceil\log_p(S_{a, b, s}(n))\right\rceil+np^{\tilde{k_p}}\left(\frac{1 - (1 - p^{-1})}{1 - p^{-1}}\right)\right)\cr&\lt \log(p)\left(\left\lceil\log_p(S_{a, b, s}(n))\right\rceil+\frac{p^{\tilde{k_p}}}{1-p}n\right)\cr&\lt \log(p)\left(\log_p(S_{a, b, s}(n))+\frac{p^{\tilde{k_p}}}{1-p}n + 1\right)\cr\end{aligned}
ここで
$ \begin{aligned}\log_p\left(S_{a, b, s}(n)\right) &= \log_p\left(\frac{a^nD - b}{a - 1}\right)\cr&\leq \log_p\left(\frac{a^nD - b}{a - 1} + \frac{b + a^n\lvert b\rvert}{a-1}\right)\cr &= \log_p\left(\frac{a^n(D + \lvert b\rvert)}{a-1}\right)\cr &= n\log_p(a) + \log_p\left(\frac{D + \lvert b\rvert}{a-1}\right)\cr\end{aligned}
であるから
$ \begin{aligned}\mathcal{L}_{a, b, s}^{(p)}(n) &\lt \log(p)\left(\log_p(S_{a, b, s}(n))+\frac{p^{\tilde{k_p}}}{1-p}n + 1\right)\cr&\leq \log(p)\left(n\log_p(a) + \log_p\left(\frac{D + \lvert b\rvert}{a-1}\right)+\frac{p^{\tilde{k_p}}}{1-p}n + 1\right)\cr &= \log(p)\left(n\left(\log_p(a) + \frac{p^{\tilde{k_p}}}{1-p}\right) + \log_p\left(\frac{D + \lvert b\rvert}{a-1}\right) + 1\right)\end{aligned}
を得る.
$ A := \log(p)\left(\log_p(a) + \frac{p^{\tilde{k_p}}}{1-p}\right).
$ B := \log(p)\left(\log_p\left(\frac{D + \lvert b\rvert}{a-1}\right) + 1\right).
$ k := A + 1, $ n_0 := \lceil B\rceil + 1とおくと, $ \forall n\in\mathbb{N}. $ n_0\lt n\implies \mathcal{L}_{a, b, s}^{(p)}(n) - kn \lt (A - k)n + B = -n+B\lt -\lceil B\rceil + B - 1\lt 0.
よって$ \mathcal{L}_{a, b, s}^{(p)}(n) = O(n). $ \Box