贡献者： int256
预备知识 数论函数
，渐进估计与阶
，最大公约数与最小公倍数
，二项式定理
本文默认若对 $n$ 求和或求积，则范围均满足 $n \ge 1$。符号 $\lfloor n \rfloor$ 表示 $n$ 的整数部分。
1. 阶
定理 1
函数 $\vartheta(x)$ 与 $\psi(x)$ 的阶是 $x$：
对于足够大的 $x$（$x \ge 2$），
\begin{equation}
Ax < \vartheta(x) < Bx, ~ Cx < \psi(x) < Dx ~ ~.
\end{equation}
2. 证明
我们首先引入一个引理并予以证明。
引理 1
\begin{equation}
\psi(x) = \vartheta(x) + \mathcal O\left( x^{1/2} (\ln x)^{2} \right) ~.
\end{equation}
证明：考虑 $\psi(x)$ 的定义，由于 $p^2 \le x$, $p^3 \le x$, $\dots$ 等价于 $p \le x^{1/2}$, $p \le x^{1/3}$, $\dots$, 故
\begin{equation}
\psi(x) = \vartheta(x) + \vartheta(x^{1/2}) + \vartheta(x^{1/3}) + \cdots = \sum_{m} \vartheta(x^{1/m}) ~.
\end{equation}
当 $x^{1/m} < 2$，也就是
\begin{equation}
m > \frac{\ln x}{\ln 2} ~~
\end{equation}
时，求和结束。由 $\vartheta(x)$ 的定义显然有 $x$ 足够大时 $\vartheta(x) < x \ln x$，故 $m \ge 2$ 时有
\begin{equation}
\vartheta(x^{1/m}) < x^{1/m} \ln x \le x^{1/2} \ln x~,
\end{equation}
且
\begin{equation}
\sum_{m \ge 2} \vartheta(x^{1/m}) = \mathcal O\left( x^{1/2} (\ln x)^{2} \right) ~.
\end{equation}
这等式成立是因为由于
式 4 ，这级数仅有 $\mathcal O(\ln x)$ 项。
将式 6 与 $\vartheta(x)$ 相加，就得到了式 3 ，就完成了证明。
这引理指出，当 $x$ 足够大时，$\vartheta(x)$ 与 $\psi(x)$ 大致相等。根据这个引理，我们只需证明对足够大的 $x$ 有 $\vartheta(x) < Bx$ 与 $\psi(x) > Cx$。因为上界与下界只需用两个数论函数中的一者约束即可。引入
\begin{equation}
M = \frac{(2m+1)!}{m! (m+1)!} = \frac{(2m+1)(2m)\cdots(m+2)}{m!} ~,
\end{equation}
这将是一个整数，且由于组合数性质，将在 $(1+1)^{2m+1}$ 的二项式展开中出现两次，故 $2M < 2^{2m+1}$ 即 $M < 2^{2m}$。考虑对于某素数 $p$，若 $m+1 < p \le 2m+1$，那么 $p$ 是 $M$ 的分子的因子，但并不是分母的因子。也就是说，
\begin{equation}
\left( \prod_{m+1 < p \le 2m+1} p \right) \mid M ~.
\end{equation}
且
\begin{equation}
\vartheta(2m+1) - \vartheta(m+1) = \sum_{m+1 < p \le 2m+1} \ln p \le \ln M < 2 m \ln 2 ~.
\end{equation}
通过归纳法可以立刻得出 $\vartheta(x) < 2x \ln 2$。就证明了 $\vartheta(x) < Bx$，另外还得到了一个更严的估计。
推论 1
对于足够大的 $n$，
\begin{equation}
\vartheta(n) < 2 n \ln n ~.
\end{equation}
下面考虑 $\psi(x)$，我们要证明 $\psi(x) > Cx$。为此引入另一引理。
引理 2
记
\begin{equation}
k(n, p) = \sum_{m\ge 1} \left\lfloor \frac{n}{p^m} \right\rfloor ~,
\end{equation}
则
\begin{equation}
n! = \prod_p p^{k(n, p)} ~.
\end{equation}
证明：这是因为 $1, 2, \dots, n$ 各数恰好包含 $\lfloor n/p \rfloor$ 个 $p$ 的倍数，恰好包含 $ \lfloor n/p^2 \rfloor$ 个 $p^2$ 的倍数，...... 依此类推。就直接完成了证明。
记
\begin{equation}
N = \frac{(2n)!}{(n!)^2} = \prod_{p \le 2n} p^{\alpha_p} ~,
\end{equation}
则利用这引理，立刻有
\begin{equation}
\alpha_p = \sum_{m=1}^{+\infty} \left( \left\lfloor \frac{2n}{p^m} \right\rfloor - 2 \left\lfloor \frac{n}{p^m} \right\rfloor\right) ~.
\end{equation}
这里指出，括号内的每一项要么是 $1$，要么是 $0$，这是由 $\lfloor 2n/p^m \rfloor$ 的奇偶性决定的。
我们考虑 $\psi(x)$ 的另一等价表达形式，是对于可能的最大的 $m$ 可以等价表示为
\begin{equation}
\psi(x) = \sum_{p^m \le x} m \ln p ~,
\end{equation}
从而这是一个最小公倍数的表示，故等价于
\begin{equation}
\psi(x) = \ln\left( [1, 2, 3, \dots, x] \right)~,
\end{equation}
或
\begin{equation}
\psi(x) = \sum_{p \le x} \left\lfloor \frac{\ln x}{\ln p} \right\rfloor \ln p ~.
\end{equation}
利用这式重新审视式 14 将不难得到
\begin{equation}
\alpha_p \le \left \lfloor \frac{\ln 2n}{\ln p} \right \rfloor ~,
\end{equation}
以及
\begin{equation}
\ln N = \sum_{p \le 2n} \alpha_p \ln p \le \sum_{p \le 2n} \left\lfloor \frac{\ln 2n}{\ln p} \right \rfloor \ln p= \psi(2n) ~.
\end{equation}
而其中，$N = (2n)!/n! \ge 2^n$，故 $\psi(2n) \ge n \ln 2$，这可以立刻得到 $\psi(x) \ge (x \ln 2)/4$，证毕！