分析学基本理论（二）

这篇博文对连分数理论和逼近算法做进一步研究

连分数逼近算法

连分数与渐进分数的差

$$\begin{gathered} x=\frac{a_{n+1}^{\prime} p_{n}+p_{n-1}}{a_{n+1}^{\prime} q_{n}+q_{n-1}} \\ \ \\ x-\frac{p_{n}}{q_{n}}=\frac{(-1)^{n}}{q_ n\left(a_{n+1}^{\prime} q_{n}+q_{n-1}\right)} \quad x-\frac{p_{0}}{q_{0}}=x-a_{0}=\frac{1}{a_{1}^{\prime}} \\ \ \\ \text{根据前面的引理, } q_{1}^{\prime}=a_{1}^{\prime}, \quad q_{n}^{\prime}=a_{n}^{\prime} q_{n-1}+q_{n-2} \ (1 < n \leqslant N) \\ \ \\ \textbf{special} \quad a_{N}=a_{N}^{\prime} \quad q_{N}^{\prime}=q_{N} \end{gathered}$$

$$\begin{gathered} \text{if} \ \ 1 \leqslant n \leqslant N - 1, \text{then} \\ \ \\ x-\frac{p_{n}}{q_{n}}=\frac{(-1)^{n}}{q_{n} q_{n+1}^{\prime}} \end{gathered}$$

$$a_{N}=1, \quad a_{N-1}^{\prime}=a_{N-1}+\frac{1}{a_{N}}=a_{N-1}+1$$

$\textbf{i)}$

$$\begin{gathered} \text{研究} \ \left|\frac{p_{n}-q_{n} x}{q_{n}}\right|=\frac{1}{q_{n} q_{n+1}^{\prime}} \Leftrightarrow\left|p_{n}-q_{n} x\right|=\frac{1}{q_{n+1}^{\prime}} \\ \ \\ \text{注意} \ q_{n+1}^{\prime} \ \text{的性质就可以了} \end{gathered}$$

$\textbf{ii)}$

$$\begin{gathered} q_{0}=1, \quad q_{1}=a_{1}, \quad q_{2}=a_{2} q_{1}+q_{0}=a_{1} a_{2}+1 \\ q_{1}=a_{1}<a_1^{\prime} <a_{1}+1 \leqslant a_{1} a_{2}+1=q_{2} \\ \ \\ q_{n+1}^{\prime}=a_{n+1}^{\prime} q_{n}+q_{n-1}, \quad a_{n+1}<a_{n+1}^{\prime}<a_{n+1}+1 \\ \ \\ 1 \leqslant n \leqslant N -2, \text{we have} \\ \ \\ \left\{\begin{gathered} q_{n+1}^{\prime}=a_{n+1}^{\prime} q_{n}+q_{n-1}>a_{n+1} q_{n}+q_{n-1}=q_{n+1} \\ q_{n+1}^{\prime}<a_{n+1} a_{n}+q_{n}+q_{n-1}=q_{n+1}+q_{n} \leqslant a_{n+2} q_{n+1}+q_{n}=q_{n+2} \end{gathered}\right. \end{gathered}$$

$$\begin{gathered} \frac{1}{q_{n+2}}<\left|p_{n}-q_{n} x\right|=\frac{1}{q_{n+1}^{\prime}}<\frac{1}{q_{n+1}} \\ \ \\ \left|p_{N}-q_{N-1} x\right|=\frac{1}{q_{N}}, p_{N}-q_{N} x=0 \\ \ \\ \left\{\begin{gathered} \frac{1}{q_{n+2}}<\left|p_{n}-q_{n} x\right|<\frac{1}{q_{n+1}} \\ \frac{1}{q_{n+3}}<\left|p_{n+1}-q_{n+1} x\right|<\frac{1}{q_{ n+2}} \end{gathered}\right. \end{gathered}$$

$|q_nx-p_n|$ 呈递减关系

$$\begin{gathered} \text{specially, we have } \\ \ \\ q_{N-1}^{\prime}=\left(a_{N-1}+1\right) q_{N-1}+q_{N-3}=q_{N-1}+q_{N-2}, \quad a_{N}=1 \\ \ \\ q_{N-1}^{\prime}=q_{N} \end{gathered}$$

$q_N$ 递增, 所以又有

$$\left.\left|x-\frac{p_{n}}{q_{n}}\right|\right. \text{ 递减}$$

逼近的结论

$$\begin{gathered} q_{n+1}>q_{n}, \quad q_{n} x-p_{n}=\frac{(-1)^{n}}{q_{n+1}^{\prime}} \\ \ \\ q_{n+1}^{\prime}=a_{n+1} q_{n}+q_{n-1}, \quad q_{n+1}^{\prime}>q_{n+1} \\ \ \\ \frac{1}{q_{n+1}^{\prime}}<\frac{1}{q_{n+1}} \Rightarrow \frac{1}{q_{n+1}^{\prime}}=\frac{1}{q_{n+1}} \cdot \delta_{n} \quad\left(0<\delta_{n}<1\right) \end{gathered}$$

$$q_{n} x-p_{n}=\frac{(-1)^{n} \delta_{n}}{q_{n+1}} \quad\left(0<\delta_{n}<1\right)$$

连分数的极限

$$\begin{gathered} n>3, \quad q_n \geqslant n \\ \left|\frac{p_{2 n}}{q_{2n}}-\frac{p_{2n-1}}{q_{2 n-1}}\right|=\frac{1}{q_{2 n} q_{2 n-1}} \leqslant \frac{1}{2 n(2 n-1)} \rightarrow 0 \end{gathered}$$

Farey数列

重要的结论

$\textbf{定理1} \quad$ 如果 $h / k$ 和$\ h^{\prime} / k^{\prime}$ 是 $\mathfrak{F_n}$ 中相邻的项, 那么
$kh'-hk'=1$

$\textbf{定理2} \quad$ 如果$h/k, \ h''/k'', \ h'/k'$ 是 $\mathfrak{F_n}$ 中 $3$ 个相连的项, 那么

$$\frac{h^{\prime \prime}}{k^{\prime \prime}}=\frac{h+h^{\prime}}{k+k^{\prime}}$$

$\textbf{定理3} \quad$ 如果 $h/k$ 和 $h'/k'$ 是 $\mathfrak{F_n}$ 中相连的两项, 那么

$$k+k'>n$$

如果定理2成立, 定理3必然成立, 因为

$$\frac{h+h^{\prime}}{k+k^{\prime}}$$

落在区间

$$\left(\frac{h}{k}, \frac{h^{\prime}}{k^{\prime}}\right)$$

中, 除非 $k+k'>n$ 成立, 否则违背 $h/k, h'/k'$ 是相邻两项

$\textbf{proof1}$
数学归纳法, 假设对于 $\mathfrak{F}_{n-1}$ 两个相连的项 $h/k, h'/k'$ 成立, 在 $\mathfrak{F}_n$ 中它们被 $h''/ k''$ 隔开

$$\begin{gathered} kh''-hk''=r > 0, \quad k''h'-h''k'=s >0 \\ \text{根据归纳假设}, \quad kh'-hk' = 1 \\ \ \\ (h'', k'') = 1, \Rightarrow (s, r)=1 \\ \ \\ \Rightarrow h'' = sh + rh', \quad k''=sk+rk' \\ \ \\ \text{考虑分数集合 }S \\ \ \\ \frac{H}{K}=\frac{\mu h+\lambda h^{\prime}}{\mu k+\lambda k^{\prime}}, \quad (\mu, \lambda) = 1\\ \ \\ \text{这是一个既约分数, 如果不是的话, 不妨设 }\\ \ \\ m | s\left(\mu h+\lambda h^{\prime}\right)+t\left(\mu k+\lambda k^{\prime}\right), \quad \forall s,t \\ \ \\ k\left(\mu h+\lambda h^{\prime}\right)-h\left(\mu k+\lambda k^{\prime}\right) = \lambda \\ h'\left(\mu h+\lambda k^{\prime}\right)-k'\left(\mu h+\lambda h^{\prime}\right) = \mu \\ \ \\ \Rightarrow m | \mu, \ m | \lambda \\ \ \\ \text{在} \ S \ \text{中取值使得} \ K \ \text{最小}, \lambda = 1, \mu = 1 \\ h''=h+h', \ k'' = k+k' \end{gathered}$$

$\textbf{proof2}$
构造法, 假设 $h/k$ 后面的项不是 $h'/k'$ , 不妨假设是 $x/y$, 那么有

$$\begin{gathered} kx-hy=1 \\ \ \\ \text{因为} \ (h, k) = 1, kx-hy=1 \ \text{有整数解} \\ \ \\ \text{另一方面, }h/k \ \text{和} x /y \ \text{是相连的两项, 那么} \\ \ \\ k+y>n \Leftrightarrow y > n - k \\ y < n \\ \ \\ \text{方程的解不妨设为} x_0, y_0 \\ \ \\ x_0+th, \ y_0+tk, \forall t \text{ 成立, 满足} \\ \ \\ 0 \leqslant n - k < y \leqslant n \ \text{当然可以取得到} \end{gathered}$$

$$\begin{gathered} kx-hy = 1 \Leftrightarrow \frac{x}{y}=\frac{h}{k}+\frac{1}{k y}>\frac{h}{k} \\ \ \\ kx-hy \geqslant 1, \quad x/y \ \text{位于} \ h/k \ \text{的后面} \\ \ \\ \text{三个}\text{ Farey }\text{项的排列是} \ \{\frac{h}{k}, \frac{h'}{k'}, \frac{x}{y}\} \\ \ \\ \frac{x}{y}-\frac{h^{\prime}}{k^{\prime}}=\frac{k^{\prime} x-h^{\prime} y}{k^{\prime} y} \geqslant \frac{1}{k^{\prime} y} \\ \ \\ \frac{h^{\prime}}{k^{\prime}}-\frac{h}{k}=\frac{h^{\prime} k-k^{\prime} h}{k k^{\prime}} \geqslant \frac{1}{k k^{\prime}} \\ \ \\ \frac{1}{k y}=\frac{k x-h y}{k y}=\frac{x}{y}-\frac{h}{k} \geqslant \frac{1}{k^{\prime} y}+\frac{1}{k k^{\prime}}=\frac{k+y}{k k^{\prime} y} >\frac{n}{k k^{\prime} y} \geqslant \frac{1}{k y} \\ \ \\ \text{矛盾, 所以} x/y= h'/k' \end{gathered}$$

Farey算法

void findNext() {
    example: 4/9
    
    get one solution of 9x-4y=1
    (x0, y0) = (1, 2)

    let 13-9 < 2+9r < 13
    
    enumerate r = 1
    x = 1 + 4r = 5
    y = 2 + 9r = 11

    5/11 is the answer
}

初等数论相关算法

素数筛法

$\textbf{Eratosthenes筛法，用v[x]标记合数}$

$$\begin{gathered} \text{从} \ x \ \text{开始} \\ \ \\ \{x^2, (x+1)x, \ldots , [N/x]\cdot x\} \text{标记为合数} \end{gathered}$$

int v[maxn];
void primes(int n) {
    Set(v, 0);
    _rep(i, 2, n) {
        if(v[i]) continue;
        cout << i << endl;
        _rep(j, i, n / i) v[i * j] = 1;
    }
}

$\textbf{线性筛法，标记最小素因子}$

$$\begin{gathered} \textbf{i)} \ \text{记录当前数的最小素因子} \ v[x] \\ \ \\ \textbf{ii)} \ \text{用递增素数列} \ \textbf{primes} \ \text{维护} [2, x]\text{ 已产生的素数集合} \\ \ \\ \textbf{iii)} \ p \in \text{primes}, p = \text{primes}[j], \ \text{在} \ x \ \text{的基础上, 累乘一个最小质因子} \ p \\ \text{需满足, } p \leqslant v[x], p \ \text{是} \ i \cdot p \ \text{的最小素因子} \end{gathered}$$

int v[maxn];
void primes(int n) {
    Set(v, 0);
    vector<int> prime;

    _rep(x, 2, n) {
        if(v[x] == 0) {
            v[x] = x;
            prime.push_back(x);
        }
        _for(i, 0, prime.size()) {
            if(prime[i] > n / x || prime[i] > v[x]) break;
            v[x * prime[i]] = prime[i];
        }
    }

    _for(i, 0, prime.size()) cout << prime[i] << endl;
}

Fermat数用于逼近

$$\begin{gathered} F_{n}=2^{2^n}+1 \\ \ \\ \text{没有大于1的公约数} \end{gathered}$$

$$\begin{gathered} x=2^{2^{n}} \\ \ \\ \frac{F_{n+k}-2}{F_{n}}=\frac{2^{2^{n+k}}-1}{2^{2^{n}}+1}=\frac{x^{2^{k}}-1}{x+1} \\ \ \\ =x^{2^k-1}-x^{2^k-2}+\cdots-1 \\ \ \\ m\left|F_{n}, \quad m\right| F_{n+k}, \quad \Rightarrow m |\left(F_{n+k}-2\right) \\ \ \\ \Rightarrow m | 2, \quad 2 \not \mathop{|} F_{n} \Rightarrow m=1 \end{gathered}$$

$$\begin{gathered} \{F_1, F_2, \cdots, F_n\} \text{能够被一个奇素数整除, 并且这些奇素数互不相同} \\ \ \\ p_{n +1} \leqslant F_n = 2^{2^n}+1 \end{gathered}$$

$\textbf{代数恒等式}$

$$\frac{a^{kl}+1}{a^{l}+1}=a^{(k-1) l}-a^{(k-2) l}+\dots+1$$

$\textbf{Euclid定理的代数证明}$
$N(x)\text{表示不超过} \ x \ \text{, 并且不能被任何} \ p > p_j \ \text{素数整除的数} \ n \ \text{的个数}$

$$\begin{gathered} n = n_1^2m, \ m \ \text{无平方因子} \\ \ \\ m=2^{b_{1}} 3^{b_{2}} \ldots p_{j}^{b_{j}} , \ b_j = \{0, 1\}\text{, 有} \ 2^j \ \text{种不同的取值} \\ \ \\ n_{1}^{2} \leqslant n \leqslant x \Rightarrow n_{1} \leqslant \sqrt{n} \leqslant \sqrt{x} \\ \ \\ m \text{有} \ 2^j \ \text{种取值, }n_1 \text{有} \sqrt{x} \text{种取值, }N(x) \leqslant 2^{j} \sqrt{x} \end{gathered}$$

$$\begin{gathered} \text{如果素数有限, 那么设所有素数为 }\{2,3,\cdots, p_j\} \\ \ \\ \text{对于每个 }\ x \ \text{ , 要么被 }[2, p_j] \text{ 中的一个整除, 要么} \ x \ \text{本身是素数} \\ \ \\ N(x) = x, \ \Rightarrow x \leqslant 2^j \sqrt{x} \\ x \leqslant 2^{2^{2j}}, \text{这个对} \ x \geqslant 2^{2^{2j}} + 1 \ \text{不成立} \end{gathered}$$

$\textbf{素数相关的级数的敛散性}$

$$\begin{gathered} \sum \frac{1}{p}=\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\dots \\ \ \\ \text{发散, 证明如下} \\ \ \\ x-N(x) \ \text{表示} \{\cdots n \cdots x\} \text{中能够被} \{p_{j+1}, p_{j+2}, \cdots \} \text{整除的数的个数} \\ \ \\ \frac{x}{p_{i+1}}+\frac{x}{p_{j+2}}+\ldots<\frac{1}{2} x, \quad x-N(x)<\frac{1}{2} x \\ \ \\ \frac{1}{2} x<N(x) \leqslant 2^j \sqrt{x}, \quad x<2^{2j+2} \\ \ \\ \text{let} \ x \geqslant 2^{2j+2} \text{, 结论不成立} \end{gathered}$$

$\pi(x) \textbf{性质}$
$\pi(x) \text{表示不超过} \ x \ \text{的素数的个数}$

$$\begin{gathered} \text{let} \ j = \pi(x), \text{这个} \ j \ \text{是可以取到的, }\text{we have} \\ \ \\ p_{j+1} > x, \quad N(x) = x \\ \ \\ x = N(x) \leqslant 2^{\pi(x)} \sqrt{x} \quad \Rightarrow 2^{\pi(x)} \geqslant \sqrt{x} \\ \ \\ \pi(x) \geqslant \frac{\ln x}{2 \ln 2} \\ \ \\ x = p_n, \quad \pi(x) = n \Rightarrow p_n \leqslant 4^n \end{gathered}$$

素数公式进一步结果

不存在任何非常数的整系数多项式 $f(n)$, 使得它对充分大的 $n$, 都取素数值
$\text{proof}$

$$\begin{gathered} x>N, \quad f(x)=a_{0} x^{k}+\ldots=y>1 \\ \ \\ \forall r, \quad f(r y+x)=a_{0}(y+x)^{k}+\ldots=a_{0}(y)^{k}+\cdots+\left(a_{0} x^{k}+\cdots\right) \\ \ \\ y | f(ry + x), r \rightarrow \infty, f(r y+x) \rightarrow \infty \\ \ \\ f(n) \text{取的到无穷多合数} \end{gathered}$$

整数模

除了 $0$ 模以外, 任何模都是某个正数 $d$ 的整数倍构成的集合

$$\begin{gathered} a \in S, \quad b \in S, \quad \Rightarrow \quad x a+y b \in S \\ \ \\ d\ \text{是}\ S\ \text{中的最小正数, }\forall z, \quad n-z d \in S \\ \ \\ \text{记余数是} \ c \ , 0 \leqslant c < d, \text{假设} \ d \ \text{最小, 因此} \\ \ \\ c = 0, \quad n = zd \end{gathered}$$

Galois理论角度理解

能以多于一种方式分解成素数乘积的数称为非正规数

$$\begin{gathered} \text{设} \ n \ \text{是最小的非正规数, 同一个素数} \ p \ \text{不可能同时在因式分解中出现} \\ \ \\ \text{否则} \ n / p \ \text{就是非正规数, } n /p < n \\ \ \\ \text{we have} \quad n = p_1p_2p_3 \cdots = q_1q_2\cdots, \ \ p_i \neq q_j \\ \ \\ p_1^2\leqslant n, \ q_1^2 \leqslant n \stackrel{p_{1} \neq q_{1}}{\Longrightarrow} \ p_1q_1 < n \\ \ \\ N = n - p_1q_1, \ 0 < N < n, N \text{为正规数} \\ \ \\ p_1 | N, q_1 | N, \ \ \Rightarrow (p_1q_1) | N \ \Rightarrow (p_1q_1) | n \\ \ \\ q_1 | (n / p_1), \text{but} \ (n / p_1) < n \ \text{为正规数} \\ \ \\ n / p_1 \text{有唯一的素数分解} \ p_2p_3\cdots \Rightarrow n = p_1p_2\cdots \text{唯一} \end{gathered}$$