浅谈一些数论型复杂度的分析方法

· · 算法·理论

前置知识

小 o 记号

考虑 a\in \{ -\infty , \infty\}\cup \mathbb{R} ，如果 \underset{ x \to a }{\lim}\dfrac{f(x)}{g(x)}=0 ，则称在极限过程 x\to a 时， f(x)=o(g(x)) ，f(x) 被称为 g(x) 的高阶无穷小。

（大 O 记号不用我讲吧）

洛必达法则

考虑定义在 a\in \{ -\infty , \infty\}\cup \mathbb{R} 的某个去心邻域内的函数 f(x), g(x)。 满足 f(x), g(x) 在这个去心邻域内可导且 g'(x)\ne 0， \underset{ x \to a }{\lim}\dfrac{f(x)}{g(x)} 为 \dfrac{0}{0} 或 \dfrac{\infty}{\infty} 形的不定式并且 \underset{ x \to a }{\lim} \dfrac{f'(x)}{g'(x)} 存在，那么 \underset{ x \to a }{\lim} \dfrac{f(x)}{g(x)}=\underset{ x \to a }{\lim} \dfrac{f'(x)}{g'(x)}。

证明涉及到微分中值定理，这里不展开。

洛必达法则一般用于证明某个复杂的代数式（尤其是无初等原函数的定积分）等于 O(f(x)) 或 o(f(x))。其中 f(x) 是某个初等函数。

Polya梦中不等式

据说是Polya在梦中发现的

\forall x>0, \ln(1+x)<x

证明：设 h(x)=x-\ln(1+x)， 容易验证 h'(x)>0 以及 h(0)=0，这意味着 \forall x>0, h(x)>0。 虽然这个不等式看起来很平凡，但在很多要分析 \ln x 求和，而 x\to 0^+ 的时候，使用这个不等式进行放缩可以极大的简化式子。

素数定理

设 \pi(x) 表示小于等于 x 的素数个数，素数定理表明

\underset{ x \to \infty }{\lim} \dfrac{\pi(x)\ln x}{x}=1

这个定理会很常用，但是我们不证。

常见的分析工具

欧拉求和公式

对于 0<x<y 以及连续可微函数 f(x):

\sum_{x< n\leq y}f(n)=\int_{x}^yf(t)\text{d}t+\int_{x}^y\{t\}f'(t)\text{d}t-\{y\}f(y)+\{x\}f(x)

证明的方法是对于每一个整数 k，使用分部积分法可以证明 f(k+1)=\int_{k}^{k+1}f(t)\text{d}t+\int_{k}^{k+1}\{ t \}f'(t)\text{d}t 然后全部加起来即可，需要稍微注意一下开头和结尾。

扩展莫比乌斯反演公式

如果 f(x) 是一个积性函数，那么

\sum_{d|n}\mu(d)f(d)=\prod_{p|n, p \text{ is prime}}(1-f(p))

证明比较显然，将右侧的所有括号展开即可。

它是莫比乌斯反演公式的推广，当取 f(x)=1 时右式变为 [n=1]，此时变成一般的莫比乌斯反演公式。

欧拉卷积公式

\mu*\text{id}=\phi

或者说

\sum_{d|n}\dfrac{n}{d}\mu(d)=\phi(n)

考虑 f(d)=\dfrac{1}{d} ，根据扩展莫比乌斯反演公式， \sum_{d|n}\dfrac{n}{d}\mu(d)=n\prod_{p|n, p \text{ is prime}}(1- \dfrac{1}{p})=\phi(n)

Abel 变换积分形式

考虑数列 \{ a_{n} \} ，设它的部分和数列 S_n=\sum_{i=1}^{n}a_{i}， 并设函数 A(x)=S_{\lfloor x \rfloor} 。另设函数 f(x) 连续可微。 设 0<y<x 那么有

\sum_{y<n\leq x} a_{n}f(n)=A(x)f(x)-A(y)f(y)-\int_{y}^xA(t)f'(t)\text{d}t

证明：将右侧积分分为三段。

只需要对于 i=\lfloor y \rfloor, i=\lfloor x \rfloor, i\in[\lfloor y \rfloor+1, \lfloor x \rfloor-1] 分别检验 A(i) 的贡献为 0 即可。

巴塞尔问题

黎曼 \zeta 函数在 2 处的取值: \zeta(2)=\sum_{i=1}^{\infty} \dfrac{1}{i^2}=\dfrac{\pi^2}{6} 这个我也不会证明，但是非常重要。

Dirichlet生成函数展开式

\sum_{d|n}f(d)=\prod_{p|n, \text{p is a prime}}(1+f(p)+f(p^2)+f(p^3)+\dots +f(p^{v_{p}(n)}))

对于积性函数 f(x) 成立。

其中 v_p(n) 表示在 n 的标准分解中 p 的次数。

证明比较显然，将右侧括号全部展开即可，但有时很有用。

分析的常用技巧

\sum_{n=1}^N\dfrac{1}{n}=1+\sum_{1<n\leq N} \dfrac{1}{n}=1+\int_{1}^N\dfrac{\text{d}t}{t}+\int_{1}^N\{t\}(-\dfrac{1}{t^2})\text{d}t

其中

\int_{1}^N\{t\}(-\dfrac{1}{t^2})\text{d}t=\int_{1}^{\infty}\{t\}(-\dfrac{1}{t^2})\text{d}t-\int_{N}^{\infty}\{t\}(-\dfrac{1}{t^2})\text{d}t

不妨设

1+\int_{1}^{\infty}\{t\}(-\dfrac{1}{t^2})\text{d}t=\gamma 而对于第二项 $$ \int_{N}^{\infty}\{t\}(-\dfrac{1}{t^2})\text{d}t<\int_{N}^{\infty}(-\dfrac{1}{t^2})\text{d}t=O(\dfrac{1}{N}) $$ 综上所述，调和级数的部分和 $$ \sum_{n=1}^N\dfrac{1}{n}=\ln N+\gamma+O(\dfrac{1}{N}) $$ ## 引理 $$ \sum_{d=1}^{x}\dfrac{\mu(d)}{d^2}=\dfrac{6}{\pi^2}+O(\dfrac{1}{x}) $$ 这个引理比较重要，在很多数论函数求和中都会用到。 **证明**：首先考虑计算 $\sum_{d=1}^{\infty} \dfrac{\mu(d)}{d^2}$, 注意 $$ \zeta(2)\sum_{d=1}^{\infty} \dfrac{\mu(d)}{d^2}=\left( \sum_{d=1}^{\infty} \dfrac{\mu(d)}{d^2} \right)\left( \sum_{i=1}^{\infty} \dfrac{1}{i^2} \right)=\sum_{k=1}^{\infty} \dfrac{\sum_{d|k}\mu(d)}{k^2}=1 $$ 所以 $\sum_{d=1}^{\infty} \dfrac{\mu(d)}{d^2}=\dfrac{1}{\zeta(2)}=\dfrac{6}{\pi^2}$。 接下来分析 $\sum_{d=x+1}^{\infty}\dfrac{\mu(d)}{d^2}$ 。它小于 $$\sum_{d=x+1}^{\infty}\dfrac{1}{d^2}<\int_{x}^{\infty} \dfrac{1}{t^2}\text{d}t=\dfrac{1}{x}$$ 所以 $\sum_{d=x+1}^{\infty}\dfrac{\mu(d)}{d^2}=O(\dfrac{1}{x})$ 。 那么 $$\sum_{d=1}^{x}\dfrac{\mu(d)}{d^2}=\sum_{d=1}^{\infty} \dfrac{\mu(d)}{d^2}-\sum_{d=x+1}^{\infty}\dfrac{\mu(d)}{d^2}=\dfrac{6}{\pi^2}+O(\dfrac{1}{x}) $$ ## 欧拉函数前缀和 $$ \sum_{i=1}^{N} \phi(i)=\dfrac{3}{\pi^2}x^2+O(x\ln x) $$ **证明**：使用欧拉卷积公式以及引理 $$ \sum_{i=1}^{x} \phi(i)=\sum_{i=1}^{x}\sum_{d|i} \mu(d) \dfrac{i}{d}=\sum_{d=1}^{x}\mu(d)\sum_{k=1}^{\lfloor \dfrac{x}{d} \rfloor}k=\sum_{d=1}^{x} \mu(d)(\dfrac{x^{2}}{2d^2}+O(\dfrac{x}{d}))= $$ $$ \dfrac{x^2}{2}\sum_{d=1}^{x} \dfrac{\mu(d)}{d^2}+O(x\log x)=\dfrac{3}{\pi^2}x^2+O(x\log x) $$ ## 欧拉函数倒数和 $$ \sum_{n=1}^{x} \dfrac{1}{\phi(n)}=O(\ln x) $$ **证明**：注意左式小于 $\sum_{n|x!} \dfrac{1}{\phi(n)}$ ，根据**Dirichlet生成函数展开式**，它小于 $$\prod_{p\leq x}(1+\dfrac{1}{p-1}+ \dfrac{1}{(p-1)p}+ \dfrac{1}{(p-1)p^2}+\dots)\sim\prod_{p\leq x}(1+\dfrac{1}{p})=\exp\left( \sum_{p\leq x}\ln(1+\dfrac{1}{p}) \right)$$ $$\leq\exp(\sum_{p\leq x} \dfrac{1}{p})=O(\ln x)$$ 其中使用了**polya梦中不等式**。 ## 埃氏筛复杂度/素数倒数和 埃氏筛复杂度为 $$O(n\sum_{p\leq n, p\text{ is prime}}\dfrac{1}{p})$$ 现在，让我们证明 $$ \sum_{p\leq x, p\text{ is prime}}\dfrac{1}{p}\sim\ln\ln x $$ 考虑设 $a_{n}=[n \text{ is prime}]$ ，然后使用 Abel 变换积分形式，得到 $$ \sum_{p\leq x, p\text{ is prime}}\dfrac{1}{p}=\sum_{n=1}^{x}[n \text{ is prime}]\dfrac{1}{n}=\pi(x) \dfrac{1}{x}+\int_{2}^x \dfrac{\pi(t)}{t^2}\text{d}t\sim \dfrac{1}{\ln x}+\int_{2}^x \dfrac{1}{t\ln t}\text{d}t $$ 使用**第一类换元法**计算得 $\int \dfrac{1}{t\ln t}\text{d}t=\ln\ln t+C$。 所以我们证明了 $$ \sum_{p\leq x, p\text{ is prime}}\dfrac{1}{p}\sim\ln\ln x $$ 这也意味着埃氏筛复杂度是 $O(n\log\log n)$ 。 ## 素数对数和/第一类切比雪夫函数 定义第一类切比雪夫函数 $$ \vartheta(x)=\sum_{p\leq x}\ln p $$ 可以证明 $\vartheta(x)=x+o(x)$。 **证明**： 类似计算素数倒数和的方法 $$ \sum_{p\leq x}\ln p=\sum_{n=1}^{x}[n \text{ is prime}]\ln n=\pi(x)\ln x-\int_{2}^x \dfrac{\pi(t)}{t}\text{d}t\sim x-\int_{2}^x \dfrac{1}{\ln t}\text{d}t $$ $\int \dfrac{1}{\ln t}\text{d}t$ 不好算，但是我们可以证明 $\int_{2}^x \dfrac{1}{\ln t}\text{d}t=o(x)$ 。设 $f(t)+C=\int \dfrac{1}{\ln t}\text{d}t$ ，计算得 $$ \underset{ x \to \infty }{\lim} \dfrac{\int_{2}^x \dfrac{1}{\ln t}\text{d}t}{x}=\underset{ x \to \infty }{\lim} f'(x)=\underset{ x \to \infty }{\lim} \dfrac{1}{\ln x}=0 $$ 所以 $\int_{2}^x \dfrac{1}{\ln t}\text{d}t=o(x)$，即 $$ \sum_{p\leq x}\ln p=x+o(x) $$