用户: TravorLZH/一个来自 Erdös 的渐近公式

在本文中, 我们将证明 Erdös 于 1948 年提出的渐近公式: $$A(x)=\sum _{\begin{array}{c}n\le x\\ (n,\phi (n))=1\end{array}}1\sim \frac{e^{-\gamma }x}{\log \log \log x},$$(1)其中 $\phi (n)$ 表示大小不超过 $n$ 且与 $n$ 互素的正整数个数. 为了方便后面的叙述, 用集合 $A$ 表示满足 $n\le x,(n,\phi (n))=1$ 的正整数.

1初等分析

很明显, 整数 $n$ 若要与 $\phi (n)$ 互素, 则其必然为无平方因子数. 否则倘若 $p^2|n$ 则有 $p(p-1)|\phi (n)$, 所以 $n$ 不能被任何素数的平方整除. 因此当 $(n,\phi (n))=1$ 时总有: $$\phi (n)=\prod _{p|n}(p-1).$$这意味着倘若 $n$ 能被素数 $p$ 整除, 则 $n$ 必然不能被任何满足 $p^{\prime }\equiv 1(\mathrm{mod}p)$ 的素数 $p^{\prime }$ 整除.

2化为筛法问题

一个解析数论研究者看到互素条件时往往会想到通过筛法来研究这个问题, 所以我们希望选择 $1<y<x$ 来将 $A(x)$ 的求和区间根据 $n$ 的最小素因子进行划分: $$A(x)=\sum _{\begin{array}{c}n\in A\\ \exists p|n\wedge p\le y\end{array}}1+\sum _{\begin{array}{c}n\in A\\ p|n\Rightarrow p>y\end{array}}1$$

3主项的产生

对于 $p|n\Rightarrow p>y$ 的部分, 我们立即根据先前的初等分析得到: $$\begin{array}{rl}\sum _{\begin{array}{c}n\le x\\ p|n\Rightarrow p>y\end{array}}1-\sum _{\begin{array}{c}n\in A\\ p|n\Rightarrow p>y\end{array}}1& \le \sum _{\begin{array}{c}n\le x\\ \exists p>y,p^2|n\end{array}}1+\sum _{y<p\le x}\sum _{\begin{array}{c}n\le x\\ \exists p^{\prime }|n\wedge p^{\prime }\equiv 1(p)\end{array}}1\\ & =\sum _{y<p\le x}\lfloor \frac{x}{p^2}\rfloor +\sum _{y<p\le x}\sum _{\begin{array}{c}y<p^{\prime }\le x\\ p^{\prime }\equiv 1(p)\end{array}}\lfloor \frac{x}{p{p}^{\prime }}\rfloor \\ & \ll \frac{x}{y}+x\sum _{y<p\le x}\frac{1}{p}\sum _{\begin{array}{c}y<p^{\prime }\le x\end{array}}\frac{1}{p^{\prime }}\\ & \ll \frac{x(\log \log x+\log y)}{y},\end{array}$$由于 $|A|\le \lfloor x\rfloor$, 所以我们必然希望选取 $y$ 使这个上界为 $O(x)$. 因此很明显我们需要 $y=O(\log x)$, 这样就有: $$\sum _{\begin{array}{c}n\le x\\ p|n\Rightarrow p>y\end{array}}1-\sum _{\begin{array}{c}n\in A\\ p|n\Rightarrow p>y\end{array}}1=O\left(\frac{x\log \log x}{y}\right)$$而此时根据 Eratosthenes 筛法, 易知 $y=o(\log x)$ 时存在 $c_0>0$ 使得: $$\sum _{\begin{array}{c}n\le x\\ p|n\Rightarrow p>y\end{array}}1=\frac{e^{-\gamma }x}{\log y}+O\left(x{e}^{-c_0\sqrt{\log y}}\right),$$所以我们为了避免误差项吞噬主项, 我们要求 $\log y/\log \log x=o(1/\log y)$, 所以设置 $y=(\log \log x)L(x)$ (其中 $L(x)=o(\log \log x)$ 单调递增) 便有: $$\begin{array}{rl}\sum _{\begin{array}{c}n\in A\\ p|n\Rightarrow p>y\end{array}}1& =\frac{e^{-\gamma }x}{\log \log \log x}\left\{1+O\left(\frac{\log L(x)}{\log \log x}\right)\right\}\\ & +O\left\{\frac{x}{L(x)}\right\}+O\left(x{e}^{-c_0\sqrt{\log \log \log x}}\right),\end{array}$$(2)

4余项的估计

对于满足 $\exists p|n\wedge p\le y$ 的部分, 我们引入 $A_p(x)$ 表示 $A$ 中最小素因子为 $p$ 的整数个数, 则有: $$A_p(x)=\sum _{\begin{array}{c}n\in A\\ p^{\prime }|n\Rightarrow p^{\prime }\ge p\end{array}}1=\sum _{\begin{array}{c}m\le x/p\\ p^{\prime }|m\Rightarrow p^{\prime }>p\\ (pm,\phi (pm))=1)\end{array}}1.$$(3)

Siegel–Walfisz 定理的应用

结合先前的初等分析, 我们知道 $A_p(x)$ 中数到的 $m$ 必然不能被满足 $p^{\prime }\equiv 1(\mathrm{mod}p)$ 的素数 $p^{\prime }$ 整除, 固当 $1\le z\le x$ 时: $$A_p(x)\le \sum _{\begin{array}{c}m\le x/p\\ p^{\prime }|m\Rightarrow p^{\prime }\not\equiv 1(p)\end{array}}1\le \sum _{\begin{array}{c}m\le x/p\\ p^{\prime }|m\wedge p^{\prime }\equiv 1(p)\Rightarrow p^{\prime }>z\end{array}}1,$$所以此时对右侧套用 Brun 筛法即得: $$A_p(x)\ll \frac{x}{p}\prod _{\begin{array}{c}{p}^{\prime }\le z\\ p^{\prime }\equiv 1(p)\end{array}}\left(1-\frac{1}{p^{\prime }}\right).$$对于最右侧, 只需估计 $p^{\prime }\equiv 1(p)$ 倒数和的下界即可. 由 Siegel–Walfisz 定理 [1] 可知 $(a,q)=1$ 时: $$\pi (x;q,a)=\frac{1}{\phi (q)}{\int }_2^x\frac{\mathrm{d}t}{\log t}+O\left(\frac{x}{{\log }^{A}x}\right),$$所以分部求和可知: $$\sum _{\begin{array}{c}{p}^{\prime }\le z\\ p^{\prime }\equiv a(q)\end{array}}\frac{1}{p^{\prime }}=\frac{1}{\phi (q)}\log \log z+O(1).$$这意味着当 $\log z=\log x/\log \log x$ 时总存在 $0<c_1<1$ 使得 $x$ 充分大时总有: $$A_p(x)<\frac{x}{p}\exp \left(-\frac{c_1\log \log x}{p}\right),$$由于 $p>\log \log x$ 时这个上界弱于平凡界 $A_p(x)\le \lfloor x/p\rfloor$, 所以 $p$ 靠近 $y$ 的部分需要分开处理: $$\sum _{p\le y}{A}_p(x)\ll x(\log \log w)\exp \left(-\frac{c_1\log \log x}{w}\right)+\sum _{w<p\le y}{A}_p(x).$$(4)

区间 $w<p\le y$ 的处理

结合 (3) 可知 Brun 筛可以帮助我们得到另一个适用于 $A_p(x)$ 的上界: $$A_p(x)\le \sum _{\begin{array}{c}m\le x/p\\ p^{\prime }|m\Rightarrow p^{\prime }>p\end{array}}1\ll \frac{x}{p}\prod _{p^{\prime }<p}\left(1-\frac{1}{p}\right)\ll \frac{x}{p\log p},$$所以有: $$\sum _{w<p\le y}{A}_p(x)\ll \frac{x}{\log w}\log \frac{\log y}{\log w}.$$此刻设置 $w=\log \log (x)/L(x)$ 便有: $$\begin{array}{rl}\sum _{w<p\le y}{A}_p(x)& \ll \frac{x}{\log \log \log x}\log \frac{\log \log x+\log L(x)}{\log \log x-L(x)}.\\ & =\frac{x}{\log \log \log x}\log \left\{1+O\left(\frac{\log L(x)}{\log \log x}\right)\right\}\\ & \ll \frac{x\log L(x)}{\log \log x(\log \log \log x)}.\end{array}$$将这个结果与 (4) 结合, 便知存在 $0<c_2<c_1$ 使得: $$\sum _{p\le y}{A}_p(x)\ll x\exp \left(-c_{2}L(x)\right)+\frac{x\log L(x)}{\log \log x(\log \log \log x)}.$$

5结论

现在带入$$\log L(x)=\frac{\log \log \log x}{\log \log \log \log x},$$便由 $\log \log \log \log x=o(\log L(x))$ 可知对于所有的 $A>0$ 均有: $$L(x){\gg }_A(\log \log \log x{)}^A,$$所以: $$\sum _{p\le y}{A}_p(x){\ll }_A\frac{x}{(\log \log \log x{)}^A}.$$再结合 (2) 便知对于所有固定的 $B>0$ 均有: $$A(x)=\frac{e^{-\gamma }x}{\log \log \log x}+O\left\{\frac{x}{(\log \log \log x{)}^B}\right\}.$$至此我们就完成了 (1) 的加强版证明.

6后记

事实上 Paul Pollack 在 2022 年给出了 $A(x)$ 的渐近级数: $$A(x)=\frac{e^{-\gamma }x}{\log \log x}\sum _{0\le k\le N}\frac{c_k}{(\log \log \log x{)}^k}+O\left\{\frac{x}{(\log \log \log x{)}^{N+2}}\right\}$$其中 $c_k$ 的计算方法详见他的论文 [3]. 但这个结果似乎与本文的结论有矛盾.

参考文献

[1]	Davenport, H. (1980). Multiplicative Number Theory (Vol. 74). Springer New York. https://doi.org/10.1007/978-1-4757-5927-3
[2]	Erdös, P. (1948). Some asymptotic formulas in number theory. J. Indian Math. Soc., 12, 75–78.
[3]	Pollack, P. (2021). Numbers which are orders only of cyclic groups. Proc. Amer. Math. Soc., 150(02), 515–524. https://doi.org/10.1090/proc/15658