给定参数下满足最大公约数下界的整数对数量求解问询

先明确问题背景：给定$N\gg0$（$N$足够大）、小正数$\epsilon>0$，且$\alpha\in\left(\frac{1}{2},\frac{3}{4}\right)$，我们要计算在整数对集合$(a,b)\in[-N^{{\alpha+\epsilon},N}{\alpha+\epsilon}]\times[-N^{{\alpha+\epsilon},N}{\alpha+\epsilon}]$中，满足$\gcd(|a|,|b|)>N^{1/3}$的整数对数量。

核心思路：补集计数 #

直接计算$\gcd> N^{1/3}$的数量比较绕，我们换个思路——先算补集（也就是$\gcd(|a|,|b|)\leq N^{1/3}$的整数对数量），再用总数量减去这个值就能得到目标结果。

步骤1：估算总整数对数量

当$N$足够大时，区间$[-N^{{\alpha+\epsilon},N}{\alpha+\epsilon}]$里的整数个数约为$2N^{\alpha+\epsilon}$（端点的+1可以忽略不计），所以总整数对数量近似为：
$$\text{总数量} \sim (2N^{{\alpha+\epsilon})}2 = 4N^{2(\alpha+\epsilon)}$$

步骤2：计算$\gcd(|a|,|b|)\leq N^{1/3}$的概率

题目里已经给出关键结论：对于任意整数$d$，$d$同时整除$|a|$和$|b|$的概率为$\frac{1}{d^{2\zeta(2)}$，其中$\zeta(2)=\frac{\pi}2}{6}$是黎曼ζ函数在2处的取值。

因为$N$极大，离散的求和可以用积分近似，所以所有同时整除$a$和$b$的最大公约数$d\leq N^{1/3}$的概率为：
$$\int_{1}^{N{1/3}}\frac{1}{x^2\zeta(2)}dx = \frac{1}{\zeta(2)}\left(1 - \frac{1}{N^{1/3}}\right)$$

步骤3：推导目标数量

$\gcd(|a|,|b|)\leq N^{1/3}$的整数对数量就是总数量乘以这个概率：
$$\text{补集数量} \sim 4N^{2(\alpha+\epsilon)} \cdot \frac{1}{\zeta(2)}\left(1 - \frac{1}{N^{1/3}}\right)$$

那么目标的$\gcd(|a|,|b|)>N^{1/3}$的数量就是：
$$\begin{align*}
\text{目标数量} &= \text{总数量} - \text{补集数量} \
&\sim 4N^{2(\alpha+\epsilon)} - 4N^{2(\alpha+\epsilon)} \cdot \frac{1}{\zeta(2)}\left(1 - \frac{1}{N^{1/3}}\right) \
&= 4N^{2(\alpha+\epsilon)}\left(1 - \frac{1}{\zeta(2)}\right) + \frac{4N^{2(\alpha+\epsilon)-1/3}}{\zeta(2)}
\end{align*}$$

简化与说明 #

代入$\zeta(2)=\frac{\pi^{2}{6}$，可以把主导项的系数简化为$1-\frac{6}{\pi}2}\approx0.392$。另外，由于$\alpha\in\left(\frac{1}{2},\frac{3}{4}\right)$，$2(\alpha+\epsilon)-\frac{1}{3}=2\alpha+2\epsilon-\frac{1}{3}>2\times\frac{1}{2}-\frac{1}{3}=\frac{2}{3}>0$，所以第二项是正的低阶修正项；当$N$趋向于无穷大时，第一项是绝对主导的部分，此时目标数量可以近似为：
$$\text{目标数量} \sim 4\left(1 - \frac{6}{\pi^2}\right)N{2(\alpha+\epsilon)}$$

内容的提问来源于stack exchange，提问作者Turbo