如何基于ψ函数证明lcm(1,…,n) < Aⁿ：LCM上界求解

这其实是个挺直接的推导，咱们从已知条件一步步拆解就行：

首先先把关键的已知信息明确下来：

• 题目给出 $\psi(n) = \log \text{lcm}(1,\dots,n)$，这直接把最小公倍数的问题转化成了对$\psi(n)$的估计；
• 另外已知 $\psi(x) = O(x)$，这个大O符号的具体含义是：存在某个常数$C > 0$和某个正整数$N$，当所有$n \geq N$时，$\psi(n) \leq Cn$（因为$\psi(x)$本身是非负的，绝对值可以直接去掉）。

接下来分两步完成证明：

第一步：处理足够大的$n$ #

对于$n \geq N$的情况，我们对等式$\psi(n) = \log \text{lcm}(1,\dots,n)$两边取自然指数，得到：
$$\text{lcm}(1,\dots,n) = e^{\psi(n)}$$
结合$\psi(n) \leq Cn$的估计，代入后就能得到：
$$\text{lcm}(1,\dots,n) \leq e^{Cn} = \left(e^C\right)n$$

第二步：处理较小的$n$ #

对于$1 \leq n < N$的情况，这是有限个正整数，对应的$\text{lcm}(1,\dots,n)$也是有限个确定的正数。我们可以计算每个$n$对应的$\left(\text{lcm}(1,\dots,n)\right)^{1/n}$，然后取这些值中的最大值，记为$M$。

第三步：确定常数$A$ #

现在只需要取$A$为$\max\left(e^C + \epsilon, M\right)$，其中$\epsilon$是任意一个小的正数（比如取$\epsilon=1$，只要保证$A > e^C$即可）。这样：

• 当$n \geq N$时，$\text{lcm}(1,\dots,n) \leq (e^C)n < A^n$；
• 当$1 \leq n < N$时，$\text{lcm}(1,\dots,n) \leq M^n \leq A^n$。

不管$n$取什么正整数，都满足$\text{lcm}(1,\dots,n) < A^n$，也就证明了存在这样的常数$A$。

额外补充一句：其实如果结合素数定理的等价形式$\psi(x) \sim x$，还能得到更精确的结论——$\log \text{lcm}(1,\dots,n) \sim n$，也就是说$\text{lcm}(1,\dots,n)$的阶是$e^{{n(1+o(1))}$，不过题目只需要证明存在上界$A}n$，用$\psi(x)=O(x)$的估计就完全足够了。

内容的提问来源于stack exchange，提问作者Dominated Convergence Theorem